vikalp14's blog

How to solve Subset Sum problem for big constraints?
By vikalp14, history, 6 years ago, In English

Question: Given a set of "n" non-negative integers, and a value "sum", determine if there is a subset of the given set with sum equal to given sum.

Input Format: 1st Line: n sum 2nd Line: a1 a2……an (Array Values)

Constraints: 1<= n <= 5000 1<= sum <= 10^7 1<= Ai <=10^5

Output Format: Yes, if sum exist No, it sum does not exist

I wanted to use this https://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/ solution But creating an array dp[5000+1][10e7+1] is not possible. So what can be done?

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

You do not need first coordinate in dp matrix, current state can be calculated from previous state — two arrays for current and previous state, or calculating values from biggest to lowest with one array will be enough. About some optimization of speed, you can use bitset, only one bit is important for calculating each possible value (1 if we can make some value till now, otherwise 0).

For example you have maximum possible sum 10 and current mask 0110100000. With adding number 3, it is same as shifting current mask for 3 places. It will be 0000110100. So, all possible values which we can make are same as bitwise or of this masks: 0110100000 or 0000110100 = 0110110100. Complexity of this solution is .

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hey @allllekssssa thanks for replying!

    Could you explain how reaching the current state from the previous state is possible when we calculate values from biggest to lowest?

    Also the optimization you mentioned is quite cool but how does adding number 3 is same as shifting the mask by 3 places? (Is is related to 2^0 + 2^1 ,if it is, then wont this requires two places)

    :)

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +9 Vote: I do not like it

      Hi,

      I will try to explain it a bit more.

      Formula for calculating DP matrix would be something like DP[i][j]= max(DP[i - 1][j] , DP[i - 1][j - Ai]). DP[i][j] — can we make sum j from first i elements. So, only current and previous conditions are important, just two arrays are enough. For iterating from biggest to lowest value we would have something like DP[j] = max(DP[j], DP[j - Ai]). It is important to iterate from biggest j to the smallest — because we didn't calculate DP[j - Ai] for current position. In case we started from the lowest to the biggest, we would have first that DP[j] = true, than DP[j + Ai] = true, than DP[j + 2Ai] = true and so on(and we have only one number Ai).

      Second thing with bitset, probably you didn't understand well. Binary representation like 0110111000 means, we can not make sum 1, we can make sum 2, we can make sum 3, we can not make sum 4, we can make sum 5 and so on (I hope you see pattern). So when you are adding new number, for example 3, it means: now you can make sum 3 for sure, you can make sum 5 for sure (because 2 was possible in previous step), we can make sum 6 ( 3 was possible in previous step), we can make sum 8 (five was possible in previous step). So if you have array of bits, and you have ones on places 2, 3, 5, now you will have ones on places 5,6,8 for sure ( it is shifting for 3 places right? ). After this observation you can do logical operation which I mentioned in the comment before.

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Just wanted to ask whether C++ map map<pair<int,int>,int> would work or not to reduce the unnecessary wastage of memory because not all the i,j pair will be used up for the solving the (n,sum) state ?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I think that you can not save on that way. In case you have array $$$2^0, 2^1, \dots,.2^{16}$$$ after 17 steps you will be able to make all numbers smaller than $$$10^5$$$ and it is too much memory immediately.

      → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain time complexity of this approach specially that divide by 32 part Thank you

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can you please share the link of question so that i can submit my solution thanks

→ Reply
»
23 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it 
int n, k;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0 ; i < n ; ++i) cin >> nums[i];
    cin >> k;
    unordered_map<int, int> seen = {{0, 1}};
    int count = 0, sum = 0;
    bool found = false;
    for (auto n: nums) {
        sum += n;
        count += seen[sum - k];
       if (seen.end() != seen.find(sum - k))
          {
            found = true;
            break; 
          }
        seen[sum]++;
    }
    if(found) cout << "Yes" << '\n';
    else cout << "No" << '\n';

Can u check this, with some test cases, see if it works

hope will pass, as max value of n is 1e5

→ Reply