-1

I just solved the subset sum problem:

Given an integer array nums of size N. You are also given an integer B, you need to find whether there exists a subset in nums whose sum is B. If there exist a subset then return 1 else return 0.

Constraints are: 1 <= N <= 100; 1 <= nums[i] <= 100; 1 <= B <= 10^5;

The way I solved this problem is as below (0/1 knapsack):

vector<int> n;
int t;
unordered_map<string, long long> m;

int helper(int i, int sum) {
    if(i>=n.size()) return sum==t;
    string str=to_string(i)+"-"+to_string(sum);
    if(m.count(str)) return m[str];

    int val=helper(i+1, sum+n[i]);
    val=max(val, helper(i+1, sum));

    return m[str]=val;
}

int Solution::solve(vector<int> &nums, int B) {
    n=nums;
    t=B;
    m.clear();
    
    return helper(0,0);
}

This gets "Accepted". However, note that all the values in nums are positive; so IMO sum will only remain the same/go on increasing. i goes on increasing, too. So, we will never encounter a value previously stored in the memoization table.

But, if I remove memoization, it results in Wrong Answer for some large test case. What am I missing? Will any recursive call ever encounter a previous state?

halfer
  • 19,824
  • 17
  • 99
  • 186
Someone
  • 611
  • 4
  • 13
  • Questions like this, where you can't provide the input that causes the failure, may be off topic: https://meta.stackoverflow.com/questions/270585/are-uva-online-judge-runtime-errors-off-topic. You may have to do more work on developing your own test cases in order to create a [mcve] and make an acceptable question. – Nate Eldredge Nov 30 '21 at 03:17
  • @NateEldredge, thank you. I am just hoping to get the logical flaw in my understanding that we never encounter previously computed values. – Someone Nov 30 '21 at 03:28
  • 1
    Not really related, but `string str=to_string(i)+"-"+to_string(sum);`: Are you aware of `std::pair`? – Nate Eldredge Nov 30 '21 at 03:57
  • 1
    `int val=helper(i+1, sum+n[i]); val=max(val, helper(i+1, sum));` the second call gets a smaller value of `sum` than the first one, so `sum` is certainly not monotone increasing. – Nate Eldredge Nov 30 '21 at 04:02
  • You could test your claim by inserting `assert(m.find(str) == m.end())`... – Nate Eldredge Nov 30 '21 at 04:04
  • Also, why use globals? You can pass the vector to your helper function by reference. – kiner_shah Nov 30 '21 at 04:07
  • 1
    If your array is `2,4,1,5, ...`, and you choose 2,4 while skipping 1,5, then you have a subproblem with i=4 and sum=6. On the other hand, if you skip 2,4 and choose 1,5, then the subproblem is i=4 and sum=6. – user3386109 Nov 30 '21 at 04:56
  • @NateEldredge, yes, but we cannot have an `unordered_map` with a `pair` as a key; so we need to use `map` instead. This increases the time complexity without any benefit, since we don't want to keep them ordered (we just need efficient lookups). Do you agree? Or am I missing something? – Someone Dec 06 '21 at 17:08
  • @Someone: "we cannot have an unordered_map with a pair as a key": You can if you provide a hash function, see e.g. https://stackoverflow.com/a/32685618/634919 – Nate Eldredge Dec 06 '21 at 17:10

1 Answers1

0

You call helper twice, the second time with the lower sum than the first. Therefore a later call to helper could indeed have the same sum as an earlier call.

@user3386109 already gave a concrete set of num that demonstrates this. As for how often, consider the case where nums = [1, 1, ..., 1] 100 times. Then without memoization you'll call helper(100, 50) 100 choose 50 = 100,891,344,545,564,193,334,812,497,256 times. Over 100 octillion calls..takes a while.

btilly
  • 43,296
  • 3
  • 59
  • 88