算法：关于“目标和”

1.添加符号=目标和

法一：递归

class Solution {
    int res = 0;
    public int findTargetSumWays(int[] nums, int S) {
        if(nums.length == 0 || nums == null) return 0;
        dfs(nums,0,0,S);
        return res;
    }
    private void dfs(int[] nums, int st, int sum, int S) {
        if(st == nums.length) {
            if(sum == S ) res++;
            return;
        }
        dfs(nums, st+1, sum+nums[st], S);
        dfs(nums, st+1, sum-nums[st], S);
    }
}

法二：转化成01背包
数组分为取正和取负的两部分
sum_p + (- sum_n) = target
sum_p*2 = target + sum(nums)
sum_p = (target+sum(nums))/2

    public static int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum < S || (sum + S) % 2 == 1) {
            return 0;
        }
        int w = (sum + S) / 2;
        int[] dp = new int[w + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int j = w; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        return dp[w];
    }

2.分割等和的两个子集

// 0-1背包动态规划
class Solution {
    public boolean canPartition(int[] nums) {
        if(nums.length < 2 || nums == null) return false;

        int sum = 0;
        for(int i=0; i<nums.length; i++) {
            sum += nums[i];

        }
        if(sum % 2 != 0) return false;
        sum = sum/2;
        boolean[] dp = new boolean[sum + 1];
        dp[0] = true;
        for (int num : nums) {
            for (int j = sum; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
                if(dp[sum]) return true;
            }
        }
        return false;
    }
}