分割等和子集
题目描述
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100 数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5] 输出: false 解释: 数组不能分割成两个元素和相等的子集.
思路一：利用回溯
每个元素都有选和不选两种可能，如果当前和等于总和的一般，直接返回，标记置为true, 如果当前和大于sum的一半，也直接返回，因为当前和已经超过了一半，没必要往下加了 1 class Solution {
2
3 public boolean flag = false;
4 public boolean canPartition(int[] nums) {
5 int sum = 0;
6 int len = nums.length;
7 // 计算总和
8 for(int i = 0; i < len; i++){
9 sum += nums[i];
10 }
11 // 如果和是奇数，那直接返回false, 因为奇数不可能分割成两个和相等的子集
12 if(sum % 2 == 1){
13 return false;
14 }
15
16 // 使用回溯判断设置标记位
17 traceBack(0, 0, nums, sum);
18 return flag;
19 }
20
21 public void traceBack(int nowSum, int nowIndex, int[] nums, int sum){
22 if(nowIndex >= nums.length){
23 return;
24 }
25 if(nowSum >= sum /2 ){
26 if(nowSum == sum / 2){
27 flag = true;
28 }
29 return;
30 }
31 // 选
32 traceBack(nowSum + nums[nowIndex], nowIndex + 1, nums, sum);
33 // 不选
34 traceBack(nowSum, nowIndex + 1, nums, sum);
35 }
36 }
超时，只通过了36/115个测试用例
复杂度分析：
时间复杂度：O(2n), 每个数都有选和不选两种可能，所以把所有情况都遍历了一遍，时间复杂度为O(2n)。
空间复杂度：O(n)。递归栈的深度最大为O(n)。
思路二：01背包动态规划
dp[i][j]表示前i个数是否能凑出和为j的数 当不算第i个数时，dp[i][j] = dp[i-1][j]; 选第i个数数时，dp[i][j] = dp[i-1][j-nums[i]] 所以状态转移方程为：dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i]]; 初值：dp[i][0]每个数都可以选和不选，所以dp[i][0] = true,即前i数都不选，则和为0，当单个元素选的时候，dp[i][nums[i]] = true， 但是在赋初值的过程中，需要判断nums[i]是否大于target， 如果大于则数组会越界，并且如果存在单个数字大于和的一半，那肯定就不能分割成两个等值的数组了，直接返回false 即可。 剪枝：如果dp[i][target]为true, 那dp[n-1][target]肯定为true 1 class Solution {
2
3 public boolean canPartition(int[] nums) {
4
5 int sum = 0;
6 int len = nums.length;
7 // 计算总和
8 for(int i = 0; i < len; i++){
9 sum += nums[i];
10 }
11 // 如果和是奇数，那直接返回false, 因为奇数不可能分割成两个和相等的子集
12 if(sum % 2 == 1){
13 return false;
14 }
15
16 int target = sum / 2;
17 boolean[][] dp = new boolean[len][target + 1];
18
19 for(int i = 0; i < len; i++){
20 dp[i][0] = true; // 单个数字不选
21 if(nums[i] > target){ // 如果存在单个数字大于和的一半，那肯定就不能分割成两个等值的数组了
22 return false;
23 }
24 dp[i][nums[i]] = true; // 单个数字选
25 }
26
27 for(int i = 1; i < len; i++){
28 for(int j = 1; j <= target; j++){
29 if(dp[i][target]){ // 剪枝，只要任何一种组合形成了和为target, 则返回true
30 return true;
31 }
32 dp[i][j] = dp[i - 1][j];
33 if(j - nums[i] >= 0){ // 为了防止数组下标越界
34 dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
35 }
36 }
37 }
38 return dp[len - 1][target];
39 }
40 }
leetcode 执行用时：63 ms > 12.98%, 内存消耗：39 MB > 42.98%
复杂度分析：
时间复杂度：O(nc)。c是和的一半，求出了所有的dp[i][j]， 所以时间复杂度为O(nc)。 空间复杂度：O(nc)。需要一个大小为 (n * (c+1))的数组，所以空间复杂度为O(nc)。思路三：空间降维
可以看到，dp[i][j] = dp[i - 1][j] || dp[i-1][j-nums[i]], dp[i][j]之和上一行的dp[i-1]有关，所以只要用一个大小为 （target + 1）一维数组，记录下上一行的dp[]值即可。但是因为 dp[i][j]用到了dp[i-1][j-nums[i]], 所以为们应该从target到0， 逆序生成新的一行dp[]值，因为如果我们正序遍历的话，那dp[i][j-nums[i]]就会被更新成新的一行的值，后面使用该数据的后就出错了，我们需要的上一个行的值。
因为倒序遍历，且 j-nums[i]作为下标，所以为了下标不越界，当 j < nums[i]就可以开始不用向下遍历了。所以减少了迭代次数，所以同时也降低了时间复杂度。
1 class Solution {
2
3 public boolean canPartition(int[] nums) {
4
5 int sum = 0;
6 int len = nums.length;
7 // 计算总和
8 for(int i = 0; i < len; i++){
9 sum += nums[i];
10 }
11 // 如果和是奇数，那直接返回false, 因为奇数不可能分割成两个和相等的子集
12 if(sum % 2 == 1){
13 return false;
14 }
15
16 int target = sum / 2;
17 boolean[] dp = new boolean[target + 1];
18
19 dp[0] = true; // 第0个数字不选
20 if(nums[0] > target){ // 如果第0个数字大于和的一半，那肯定就不能分割成两个等值的数组了
21 return false;
22 }
23 dp[nums[0]] = true; // 第0个数字选
24
25 for(int i = 1; i < len; i++){
26 for(int j = target; j >= nums[i]; j--){
27 if(dp[target]){ // 剪枝，只要任何一种组合形成了和为target, 则返回true
28 return true;
29 }
30 dp[j] = dp[j] || dp[j - nums[i]];
31 }
32 }
33 return dp[target];
34 }
35 }
leetcode 执行用时：20 ms > 82.32%, 内存消耗：37.9 MB > 81.35%
复杂度分析：
时间复杂度：O(nc)。同样求出了每个i对应的 dp[j], 但是因为 j > nums[i]时即可停止本轮迭代，所以一定程度上减少了迭代次数，所以运行时间比思路二短一些。但是总的时间复杂度还是O(nc)。空间复杂度：O(c)。需要一个大小为 c+1的数组，所以空间复杂度为O(c)。