第一题：494. Target Sum
You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
Find out how many ways to assign symbols to make sum of integers equal to target S.
Example 1:
Input: nums is [1, 1, 1, 1, 1], S is 3. Output: 5 Explanation: -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 There are 5 ways to assign symbols to make the sum of nums be
【问题分析】
1、该问题求解数组中数字只和等于目标值的方案个数，每个数字的符号可以为正或负(减整数等于加负数)。
2、该问题和矩阵链乘很相似，是典型的动态规划问题
3、举例说明: nums = {1,2,3,4,5}, target=3, 一种可行的方案是+1-2+3-4+5 = 3
该方案中数组元素可以分为两组，一组是数字符号为正(P={1,3,5})，另一组数字符号为负(N={2,4})
因此: sum(1,3,5) - sum(2,4) = target
sum(1,3,5) - sum(2,4) + sum(1,3,5) + sum(2,4) = target + sum(1,3,5) + sum(2,4)
2sum(1,3,5) = target + sum(1,3,5) + sum(2,4)
2sum(P) = target + sum(nums)
sum(P) = (target + sum(nums)) / 2
由于target和sum(nums)是固定值，因此原始问题转化为求解nums中子集的和等于sum(P)的方案个数问题
4、求解nums中子集合只和为sum(P)的方案个数(nums中所有元素都是非负)
该问题可以通过动态规划算法求解
举例说明：给定集合nums={1,2,3,4,5}, 求解子集，使子集中元素之和等于9 = new_target = sum(P) = (target+sum(nums))/2
定义dp[10]数组, dp[10] = {1,0,0,0,0,0,0,0,0,0}
dp[i]表示子集合元素之和等于当前目标值的方案个数, 当前目标值等于9减去当前元素值
当前元素等于1时，dp[9] = dp[9] + dp[9-1]
dp[8] = dp[8] + dp[8-1]
...
dp[1] = dp[1] + dp[1-1]
当前元素等于2时，dp[9] = dp[9] + dp[9-2]
dp[8] = dp[8] + dp[8-2]
...
dp[2] = dp[2] + dp[2-2]
当前元素等于3时，dp[9] = dp[9] + dp[9-3]
dp[8] = dp[8] + dp[8-3]
...
dp[3] = dp[3] + dp[3-3]
当前元素等于4时，
...
当前元素等于5时，
...
dp[5] = dp[5] + dp[5-5]
最后返回dp[9]即是所求的解
int findTargetSumWays(vector<int>& nums, int S) { int len = nums.size(); if(len <= 0){ return -1; } int sum = 0; for(int i = 0; i < len; i++){ sum += nums[i]; } if(sum < S || (sum + S) & 1){ //如果是奇数的话则结果为0，诸如nums={1,1,1,1,1},target=2,确实结果为0 return 0; } else{ return subsetSum(nums,(sum + S) >> 1); } } int subsetSum(vector<int>& nums, int target){ vector<int> dp(target+1,0); dp[0] = 1; for(int i = 0; i < nums.size(); i++){ for(int j = target; j >= nums[i]; j--){ dp[j] += dp[j-nums[i]]; } } return dp[target]; }简介一点的代码： int findTargetSumWays(vector<int>& nums, int S) { int sum; sum = accumulate(nums.begin(),nums.end(),0); //第三个参数是求和的初始值，对nums中的每个元素进行求和 return (sum < S || (sum + S) & 1) ? 0 : subsetSum(nums,(sum + S) >> 1); } int subsetSum(vector<int>& nums, int target){ vector<int> dp(target+1,0); dp[0] = 1; for(int i = 0; i < nums.size(); i++){ for(int j = target; j >= nums[i]; j--){ dp[j] += dp[j-nums[i]]; } } return dp[target]; } 深度优先搜索：分析：深度优先搜索，尝试每次添加+或者-，当当前cnt为nums数组的大小的时候，判断sum与S是否相等，如果相等就result++。sum为当前cnt步数情况下的前面所有部分的总和
int result; int findTargetSumWays(vector<int>& nums, int S) { dfs(0,0,nums,S); return result; } void dfs(int sum, int cnt,vector<int>& nums, int S){ if(cnt == nums.size()) { if(sum == S) result++; return ; } dfs(sum + nums[cnt], cnt + 1, nums, S); dfs(sum - nums[cnt], cnt + 1, nums, S); } 第二题：416. Partition Equal Subset SumGiven a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Note:
Each of the array element will not exceed 100.The array size will not exceed 200.
Example 1:
Input: [1, 5, 11, 5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: [1, 2, 3, 5] Output: false Explanation: The array cannot be partitioned into equal sum subsets.和上题思路类似，这题target相当于数组中所有元素和的一半，故动态规划代码如下：
bool canPartition(vector<int>& nums) { int sum; sum = accumulate(nums.begin(),nums.end(),0); //第三个参数是求和的初始值，对nums中的每个元素进行求和 int target = sum >> 1; if(sum & 1) return false; vector<int> dp(target+1,0); dp[0] = 1; for(int i = 0; i < nums.size(); i++){ for(int j = target; j >= nums[i]; j--){ dp[j] = dp[j] || dp[j-nums[i]]; } } return dp[target]; } dfs回溯法代码如下： bool backtrack(vector<int>& nums, int start, int target) { if (target <= 0) return target == 0; for (int i = start; i < nums.size(); i++) if (backtrack(nums, i + 1, target - nums[i])) return true; return false; } bool canPartition(vector<int>& nums) { int sum = accumulate(nums.begin(), nums.end(), 0); return !(sum & 1) && backtrack(nums, 0, sum >> 1); }
