Leetcode-494. 目标和

494. 目标和
给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例：

输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5
解释：

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

一共有5种方法让最终目标和为3。
运行结果

解题思路
利用子集划分思想
只有+和-。我们将数组分为A（+）和B（-）两个子集
那么sum(A)-sum(B)=S----->sum(A)=S+sum(B)=2S+sum(B)+sum(A)=2S+sum(nums)---已知数
这也就转换成了给定一个数组，求子集和为target有几种子集划分方式===典型的0-1背包问题
然后利用动态规划求解背包问题
dp[i][j]:在nums的前i个元素中子集和为j的结果数
具体见注释
可选优化---将二维数组降维到一维（有点难，有思路即可）
java代码

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int sum=0;
        for(int n:nums){
            sum += n;
        }
        //无法子集划分
        if(sum < S || (sum + S) % 2 == 1){
            return 0;
        }
        return subsets(nums,(sum+S)/2);
    }
    //求数组中有多少子集和为target
    public int subsets(int[] nums , int target){
        int n=nums.length;
        //dp[i][j]:在nums的前i个元素中子集和为j的结果数
        int[][] dp=new int[n+1][target+1];
        //dp[0][..]=0-----无元素无法完成，初值即为0
        //base case:和为0只有空集
        for(int i=0;i<=n;i++){
            dp[i][0]=1;
        }
        for(int i=1;i<=n;i++){
            for(int j=0;j<=target;j++){
                if(j-nums[i-1] >= 0){
                    //对于装和不装该物品
                    dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]];
                }
                else{
                    //容量不足，只能不装
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        return dp[n][target];
    }
}