mardi 24 décembre 2019

C++ DP solution to LeetCode #377, does this code have a bug?

This C++ solution is a direct translation of the top voted Java solution in the discussion forum. My own G++ compiler compiles and runs it just fine with this test case however the LeetCode submission would yield an error (please have a quick try).

I would think memory is initialized properly and bounds checks are in place. What could be the problem?

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for (int i = 1; i < dp.size(); i++) {
            for (int j = 0; j < nums.size(); j++) {
                if (i - nums[j] >= 0) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }
};

int main(int argc, char** argv) {
    vector<int> nums {
        3, 33, 333,
    };
    cout << Solution().combinationSum4(nums, 10000) << endl;
    return 0;
}

Test case:

[3,33,333]
10000

Error message:

Line 9: Char 17: runtime error: signed integer overflow: 357856184 + 1941940377 cannot be represented in type 'int' (solution.cpp)

Aucun commentaire:

Enregistrer un commentaire