题目描述

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

1
2
3
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

具体见题目详解。

算法思路

这个题目确实有点气煞我也，因为就在不久前，我做了一道很类似的题目，当时觉得自己弄懂了……结果到头来还是在深搜+剪枝，最后时间复杂度过不去，最开始的一版代码很简单：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    void dfs(vector<int> &nums, int target, int now, int index) {
        if (now == target) {
            ans = 1;
        }
        if (index >= nums.size() || now > target || ans) {
            return;
        }
        dfs(nums, target, now + nums[index], index + 1);
        dfs(nums, target, now, index + 1);
    }
public:
    int ans;
    bool canPartition(vector<int>& nums) {
        // 深搜 sum(nums) / 2即可
        int numsum = accumulate(nums.begin(), nums.end(), 0);
        if (numsum % 2) {
            return false;
        } 
        ans = 0;
        dfs(nums, numsum / 2, 0, 0);
        return ans ? true : false;
    }
};

其实我做的时候就想到前几天那个凑数字的题了，但是无论如何都想不起来状态转移方程是啥了，哎，无奈之下看了官方的题解才做出来，思路和状态转移方程就不写了，代码里有：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        // dp[i][j]表示从[0~i]选取若干数字是否能组成j
        // 边界条件:
        // i = 0, dp[0][0] = 1, dp[0][nums[0]] = 1, dp[0][others] = 0
        // j = 0, dp[any][0] = 1;
        int numsum = accumulate(nums.begin(), nums.end(), 0);
        int n = nums.size();
        sort(nums.begin(), nums.end());
        if (numsum % 2 || nums[n - 1] > numsum / 2) {
            return false;
        }
        vector< vector<int> > dp(n, vector<int>(numsum / 2 + 1, 0));
        dp[0][0] = 1; dp[0][nums[0]] = 1;
        for (int i = 0; i < n; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < numsum / 2 + 1; j++) {
                // nums[i] <= j
                // 则nums[i]可取可不取，如果不取，就相当于从[0~i-1]挑选数字
                // 如果取,那就相当于要从[0~i-1]凑出j - nums[i] 
                if (nums[i] <= j) {
                    dp[i][j] = (dp[i-1][j] || dp[i-1][j-nums[i]]) ? 1 : 0;
                }
                else {
                    // nums[i] > j，nums[i]必然不可取
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[n - 1][numsum / 2] == 1 ? true : false;
    }
};

只能说千万不要因为做出来两道dp就以为自己行了，算法这个事儿真的跟智商挂钩，像我这种庸才学一辈子可能也不懂算法的精髓，只能照猫画虎。哦不对，照猫画虎也画不出来hhhhh