DP overflow

377. Combination Sum IV

https://leetcode.com/problems/combination-sum-iv/

The following code, if we don’t use unsigned int or unsigned long long, we will get overflow at the test case of

[3,33,333] 10000

It is interesting to see that dp[396] will have a super large number.

1941940377

Why we get this number?

396 = 3*132

one way by using 132 3s

396 = 33*12

We have bunch of ways to combine 33 and 3. Such as

1, 33

2,33

3,33

…

we will have approximate 2^(132–10) in total

it will makes the result very large.

396=333+63

This explains why we will get overflow.

Solve approach: using large size int such as unsigned int, or unsigned long long

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<unsigned long long> dp(target+1, 0);
        dp[0] = 1;
        for (unsigned long long sum=0;sum<=target;++sum){
            for(auto &num:nums){
                unsigned long long new_sum = sum+(unsigned long long)num;
                if (new_sum <= target){
                    dp[new_sum]+=dp[sum];
                }
            }
        }
        return int(dp[target]);
        
    }
};

int 4bytes -2147483648 to 2147483647

unsigned int 4bytes 0 to 4294967295

Reference

>>> 2**16-1
65535
>>> 2**32-1
4294967295
>>> 2**64-1
18446744073709551615
>>> 2**31-1
2147483647