目标和
这道题根本还是回到了在数组中找到一个集合，使得该集合与其余部分之差为target，通过公式推导：
我们可以知道 该集合的值为：（sum-target）/2;
回溯法
目的是找到和为**（sum-target）/2** 的种类
class Solution { public: int result = 0; void backtracking(vector<int>& nums, int target ,int deep ,int sum) { if(sum > target)return; if(sum == target)result++; if(deep == nums.size()) return; //从任一点开始 for(int i= deep ; i < nums.size() ;i++) { backtracking(nums,target , i+1 , sum + nums[i]); } return; } int findTargetSumWays(vector<int>& nums, int target) { int sum = 0 , diff = 0; for(auto it:nums) sum += it; diff = sum - target; if( diff<0 || diff%2==1 ) return 0; //回溯找diff/2 backtracking(nums,diff/2,0 ,0); return result; } };
动态规划
1.背包定义： dp[i][j] , i是使用0-i的元素，j是背包容量，dp[i][j]是使用这么多个元素恰好凑成j的情况
2.初始化：dp[0][0]为1,装满容量为0的背包，有一种方法。dp[0][j]，看第一个元素的大小情况，进行赋值1(如果第一个元素为0.则dp[0][0]应该为2)，其他层的根据第一层改变.
3.遍历顺序：从上往下
4.递推公式： dp[i][j]=dp[i-1][j]（不需要num[i]就能够凑出j的情况）+dp[i-1][j-nums[i]]；（需要num[i]凑出j空间的情况） 最终就能实现，从0-i元素当中组合，得到target的所有情况。
class Solution { public: int findTargetSumWays(vector<int>& nums, int target) { int sum = 0 , diff = 0; for(auto it:nums) sum += it; diff = sum - target; if( diff<0 || diff%2==1 ) return 0; vector<vector<int>> dp( nums.size() , vector<int>(diff/2 + 1 , 0) ) ; dp[0][0] = 1; for(int j=0 ; j<(diff)/2+1 ; j++) if(j==nums[0]) dp[0][j] += 1; for(int i=1 ; i<nums.size() ;i++) { for(int j=0 ; j<(diff)/2+1 ; j++) { if(j>=nums[i]) dp[i][j] = dp[i-1][j] + dp[i-1][ j - nums[i]] ; else dp[i][j] = dp[i-1][j]; } } return dp[nums.size()-1][(diff)/2]; } };
二刷
class Solution { public: int findTargetSumWays(vector<int>& nums, int target) { int sum = 0; for(auto it:nums) sum += it; if((target+sum)%2 == 1 || abs(target) > sum) return 0; //result - (sum - result) = target int result = (target+sum)/2; vector<int> dp(result+1 , 0); dp[0]=1; for(int i=0 ; i<nums.size();i++) { for(int j=result ; j>=nums[i];j--) { dp[j] += dp[j-nums[i]]; } } return dp[result]; } };
