2022.05.19(LC

class Solution {
    int ans = 0;
    public int findTargetSumWays(int[] nums, int target) {
        dfs(nums, target, 0, 0);
        return ans;
    }
    public void dfs(int[] nums, int target, int i, int sum){
        //数组遍历结束
        if(i == nums.length){
            if(sum == target) ans++;
            return;
        }
        dfs(nums, target, i + 1, sum + nums[i]);
        dfs(nums, target, i + 1, sum - nums[i]);
    }
}

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        //数组的元素和为sum，假设正子集和为sumP，负子集和为sumN
        //如果可以构造一个表达式，则sumP + sumN = target
        //而sumP - sumN = sum -->2 * sumP = sum + target
        //可以得到：sumP = (sum + target) / 2，sum + target 为偶数
        //所以可以转化为01背包问题，求组合成正子集和sumP的方式有多少种
        if (sum < target || (sum + target) % 2 == 1) return 0;
        int goal = (sum + target) / 2;
        int[] dp = new int[goal + 1];
        //当没有任何元素可以选取时，元素和只能是 0，对应的方案数是 1
        dp[0] = 1;
        for (int num : nums) {
            for (int j = goal; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        return dp[goal];
    }
    
}