Sum <= 1000


  • 0
    I
    class Solution {
    public:
        int findTargetSumWays(vector<int>& nums, int S) {
            if (nums.empty()) return 0;
    
            int size = nums.size();
    
            vector<vector<int>> dp(size, vector<int>(2001, 0));
            dp[0][-nums[0] + 1000]++;
            dp[0][nums[0] + 1000]++;
    
            for (int i = 1; i < size; i++) {
                for (int j = 0; j < 2001; j++) {
                    if (j - nums[i] >= 0) dp[i][j] += dp[i - 1][j - nums[i]];
                    if (j + nums[i] <= 2000) dp[i][j] += dp[i - 1][j + nums[i]];
                }
            }
    
            S += 1000;
            if (S >= 0 && S <= 2000) return dp[size - 1][S];
            return 0;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.