1、LeetCode416. 分割等和子集
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
注意:
- 每个数组中的元素不会超过 100
- 数组的大小不会超过 200
1.1、动态规划Ⅰ
算法：
1、定义dp[i][j]:包重 j 装前 i 件物品是否可以恰好装满
第i件物品不进包依赖前i-1件物品是否能够装满,dp[i][j] = dp[i-1][j]
第i件物品进包依赖前i-1件物品在包重为j-nums[i-1]时的状态,dp[i][j] = dp[i-1][j- nums[i-1]]
2、状态方程：dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
3、0-1背包第i件物品的状态仅依赖前i-1件的状态。
public boolean canPartition(int[] nums) {if(nums == null || nums.length <= 1){return false;}int sum = 0;for(int i = 0;i < nums.length; i++){sum += nums[i];}if((sum & 1) == 1){return false;}sum = sum >> 1;boolean [][]dp = new boolean[nums.length+1][sum + 1];dp[0][0] = true;for(int i = 1;i <= nums.length;i++){for(int j = 0; j <= sum; j++){if(j >= nums[i-1]){dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];}else{dp[i][j] = dp[i-1][j];}}if(dp[i][sum]){return true;}}return false;}
压缩成一维状态空间：
....boolean []dp = new boolean[sum + 1];dp[0] = true;for(int i = 1;i <= nums.length;i++){for(int j = sum; j >= 0; j--){//降序遍历if(j >= nums[i-1]){dp[j] = dp[j] || dp[j-nums[i-1]];}}if(dp[sum]){return true;}}...
1.2、动态规划Ⅱ
算法：
1、定义dp[i][j]：包重为 j 的前i件物品的最大价值，这里的价值取物品的重量即wt[i] = val[i]
即包重为 j 承载前 i 件物品的最大重量。
2、总是试图填充包中的空隙使其获得包中承载的物品最重，因此有状态方程：
dp[i][j] = max(dp[i-1][j],dp[i-1][j-nums[i-1]] + nums[i-1]);
该方程满足j >= dp[i][j]，即包中的价值(物品总重量)不会超过包重;
3、当dp[i][targetSum] == targetSum时满足条件直接返回
public boolean canPartition(int[] nums) {if(nums == null || nums.length ==0){return false;}int sum = 0;for(int i=0;i<nums.length;i++){sum += nums[i];}if((sum & 1) == 1){return false;}sum = sum >> 1;int [][]dp = new int[nums.length + 1][sum + 1];for(int i = 1; i < nums.length; i++){for(int j = 0; j <= sum; j++){if(j >= nums[i-1]){dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-nums[i-1]] + nums[i-1]); }else{dp[i][j] = dp[i-1][j];}}if(dp[i][sum] == sum){return true;}}return false;}
压缩空间：dp[j] = max(dp[j],dp[j-nums[i-1]] + nums[i-1]);
....
int []dp = new int[sum + 1];
for(int i = 1; i < nums.length; i++){for(int j = sum; j >= 0; j--){//遍历包重必须是降序if(j >= nums[i-1]){dp[j] = Math.max(dp[j],dp[j-nums[i-1]] + nums[i-1]); }}if(dp[sum] == sum){return true;}
}
return false;
....
3、回溯算法+二分查找
算法：
1、列举出数组的所有非空子集，计算子集之和是否为target(sum/2)
2、逐次寻找 1个、2个、..n个元素组合，用目标值逐次减去已经找过的元素，例如当寻找2个值的时候用需要
用目标值减去第一个元素，即target - nums{i]得到新的目标值在剩余元素nums[i+1,,,num.length]中继续查找
3、可以先对数组进行排序后，用二分查找，同时由于数组已经排序可以方便的去除重复元素形成的组合(这一点非常重要，否侧算法超时)
public boolean canPartition(int[] nums) {if(nums == null || nums.length <= 1){return false;}Arrays.sort(nums);int sum =0;for(int i=0;i< nums.length;i++){sum += nums[i];}if((sum & 1) == 1){return false;}else{return canPartition(nums,0,sum >> 1);} }//回溯 + 二分查找public boolean canPartition(int[] nums,int start,int target) {if(start == nums.length || nums[start] > target){return false;}if(Arrays.binarySearch(nums,start,nums.length,target) >= start){return true;}for(int i = start;i < nums.length;i++){if(i > start && nums[i] == nums[i-1]){continue;//去除重复元素很重要，否则超时}if(canPartition(nums,i + 1,target - nums[i])){//找到则立刻返回return true;}}return false;}
2、LeetCode494. 目标和
给定一个非负整数数组，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。
提示：
- 数组非空，且长度不会超过 20 。
- 初始的数组的和不会超过 1000 。
- 保证返回的最终结果能被 32 位整数存下。
3、LeetCode474. 一和零
在计算机界中，我们总是追求用有限的资源获取最大的收益。现在，假设你分别支配着 m 个 0 和 n 个 1。另外，还有一个仅包含 0 和 1 字符串的数组。你的任务是使用给定的 m 个 0 和 n 个 1 ，找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。
示例 1:
输入: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
输出: 4
解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出，即 "10","0001","1","0" 。示例 2:
输入: Array = {"10", "0", "1"}, m = 1, n = 1
输出: 2
解释: 你可以拼出 "10"，但之后就没有剩余数字了。更好的选择是拼出 "0" 和 "1" 。
注意:
- 给定 0 和 1 的数量都不会超过 100。
- 给定字符串数组的长度不会超过 600。