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

Unable to parse markup [type=CF_TEX]

. With adding number 3, it is same as shifting current mask for 3 places. It will be

Unable to parse markup [type=CF_TEX]

. So, all possible values which we can make are same as bitwise or of this masks:

Unable to parse markup [type=CF_TEX]

or

Unable to parse markup [type=CF_TEX]

=

Unable to parse markup [type=CF_TEX]

. Complexity of this solution is

Unable to parse markup [type=CF_TEX]

.
→ 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

      Unable to parse markup [type=CF_TEX]

      ,

      Unable to parse markup [type=CF_TEX]

      ). 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] =

      Unable to parse markup [type=CF_TEX]

      . It is important to iterate from biggest j to the smallest — because we didn't calculate

      Unable to parse markup [type=CF_TEX]

      for current position. In case we started from the lowest to the biggest, we would have first that

      Unable to parse markup [type=CF_TEX]

      , than

      Unable to parse markup [type=CF_TEX]

      , than

      Unable to parse markup [type=CF_TEX]

      and so on(and we have only one number Ai).

      Second thing with bitset, probably you didn't understand well. Binary representation like

      Unable to parse markup [type=CF_TEX]

      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

      Unable to parse markup [type=CF_MATHJAX]

      after 17 steps you will be able to make all numbers smaller than $$$10^5$$$ and it is too much memory immediately.
      → Reply
  • »
    »
    2 years 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
»
2 years 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