/*    这个题两个地方没想到：    第一个：我们把最后的结果分成两部分，一部分是正数的，一部分是负数的，他们的和分别用p和n表示    那么 p-n = s        2p = s+sum        p = (s+sum)/2        由于s和sum是固定的，所以只要找到能组成p的子序列种数就行    第二个：寻找能组成目标值的组合数（直接把做法背下来）     */    public int findTargetSumWays(int[] nums, int S) {        int sum = 0;        for (int num :                nums) {            sum += num;        }        return (sum < S || (sum+S)%2 > 0)?0:dpfun(nums,(sum+S)/2);    }    public int dpfun(int[] nums,int s)    {        //dp[i]是组成目标值为i的组合数        int[] dp = new int[s+1];        dp[0] = 1;        for (int num :                nums) {            //一开始考虑这里为什么是倒着。倒着的话最后一次，较大的数不是用旧的数组成的吗，也就是说在较大的数更新后，比它小的数又更新了，这不就不对吗            //后来想了想，就是不能用更新后的数来组成新的数，因为每次组成数的时候都是用上当前的数num，但是这个数只能用一次，比如组成4的时候用了，组成5的时候就不能num+4了，因为4的组成成分里有num            //倒着做就是为了小的数更新不干扰大的数            //每次把数组中的一个数作为当前数，从大到小更新一遍dp 　　　　　　　//每一个num，更新一遍大于num，小于target的数的组合数，因为又有了一种新的组合元素。            //dp[s] = dp[s] + dp[s-num]            for (int i = s; i >=num ; i--) {                dp[i] += dp[i-num];            }        }        return dp[s];    }