Latest dp c++ solution, handle input nums contain zeros


  • 0
    Z

    Input case: [0, 0, 0, 0, 0, 0, 0, 0, 1], S = 1
    Output: 256

    class Solution {
    public:
        int findTargetSumWays(vector<int>& nums, int S) {
            int target = 0;
            int zeros = 0;
            vector<int> new_nums;
            for (int i = 0; i < nums.size(); ++i) {
                target += nums[i];
                if (nums[i] == 0)
                    zeros++;
                else
                    new_nums.push_back(nums[i]);
            }
            nums = new_nums;
            if (target < S) return 0;
            target += S;
            if (target % 2 != 0) return 0;
            target /= 2;
            int dp[target + 1];
            memset(dp, 0, sizeof(dp));
            dp[0] = 1;
            for (int i = 0; i < nums.size(); ++i) {
                for (int j = target; j >= 1; --j) {
                    if (j >= nums[i]) {
                        dp[j] = dp[j] + dp[j - nums[i]];
                    }
                }
            }
            return dp[target] * (1 << zeros);
        }
    };

Log in to reply
 

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