494. Target Sum

https://leetcode.com/problems/target-sum/description/

You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Thoughts

整数数组中选一部分取负，其它不变，问一共有多少种取法能让最后的和等于S。把集合的数看成两个子集，满足sum(P) - sum(!P) = target 和sum(P) + sum(!P) = sum => sum(P) = (sum + target)/2，也就是找和为(sum+target)/2的子集数目，01背包。

Code

/*
 * @lc app=leetcode id=494 lang=cpp
 *
 * [494] Target Sum
 */

// @lc code=start
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        const int N = nums.size(), sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum < S || (sum + S) % 2 != 0) return 0;
        const int V = (sum + S) / 2;
        vector<int> dp(V + 1, 0);
        for (int i = 0; i <= N; ++i) dp[0] = 1;
        for (int i = 1; i <= N; ++i) {
            for (int j = V; j >= 0; --j) {
                dp[j] += (j >= nums[i - 1]) ? dp[j - nums[i - 1]] : 0;
            }
        }
        return dp[V];
    }
};
// @lc code=end

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        if (sum < target || (target + sum) % 2 == 1) {
            return 0;
        }
        int V = (target + sum) / 2;
        int[] f = new int[V + 1];
        f[0] = 1;
        for (int num : nums) {
            for (int j = V; j >= num; j--) {
                f[j] += f[j - num];
            }
        }

        return f[V];
    }
}