Description

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

Examples

1
2
3
4
5
输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].
1
2
3
4
5
输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.

Thought

由于所给数组的规模不确定，所要分成的数组的规模的大小，所以不能使用循环嵌套的方法遍历所有可能性，即不能在多项式时间内解决（NP问题）。如果使用贪心则只能求得局部最优解而不能取得全局的解。因此此题需要使用记忆性搜索或者动态规划的方法来解决。

考虑到对于任意一个数我们都有选择或者不选这两种选择，因为我们可以开一个二维数组dp[n][target+1]，其中n表示nums数组中的数据大小。target表示将nums数组中的数据进行累计求和后得到的和sum2\frac{sum}{2}，对于数组中的任意位置dp[i][j],表示的是当选择到第i个数的时候是否可以达到j的值。

在进行动态规划之前我们应当去考虑临界条件。首先，当nums数组的规模小于2时，必定没有解，因此直接返回false；当maxNum大于n2\frac{n}{2}时，也不可能找到解，因此直接返回false；当sum为奇数时，说明不可能等分为两个同样的集合，因此也直接返回false。

首先要将整个dp数组进行初始化，即将整个数组都设为false。然后我们需要考虑对dp数组的初始状态进行设置。考虑到当j=0即当没有num被选择时，应当将这一列全部设置为true。当nums[0]被选择时，也应当将dp[0][nums[0]]的值设置为true。

将dp数组初始化之后我们就需要对数组进行状态转移，考虑到对于任意的i,j的状态数组dp[i][j]，当此时所选择的nums[i]大于j时，此时nums[i]一定不能被选择，那么此时的状态即为dp[i][j] = dp[i-1][j],当nums[i]<j时，那么表明当前的数据nums[i]可以被选择，那么此时的状态就可以有两种选择dp[i-1][j]和dp[i-1][j-nums[i]]，因此状态转移方程如下：

dp[i][j]={dp[i−1][j]dp[i−1][j]∣dp[i−1][j−nums[i]]dp[i][j] = \begin{cases} dp[i-1][j] \\ dp[i-1][j] \quad|\quad dp[i-1][j-nums[i]] \end{cases}

Solution

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function(nums) {
    const n = nums.length;
    if(n<2)return false;
    let sum = 0;

    let maxNum = 0;
    for(let i=0; i<n; i++){
        sum+=nums[i];
        if(nums[i]>maxNum){
            maxNum = nums[i]
        }
    }

    //
    if(sum & 1)return false;

    const target = sum/2;
    if(maxNum>target)return false;


    let dp = new Array(n);

    //initial dp array
    for(let i=0;i<n;i++){
        dp[i] = new Array(target+1);
        for(let j=0;j<=target;j++){
            dp[i][j] = false;
        }
    }


    //set dp[i][0] = 1 because no value is selected
    for(let i=0;i<n;i++){
        dp[i][0] = true;
    }

    //initial
    dp[0][nums[0]] = true;

    //dp

    for(let i=1;i<n;i++){
        let num = nums[i];
        for(let j=1;j<=target;j++){
            if(j<num){
                dp[i][j] = dp[i-1][j];
            }else{
                dp[i][j] = dp[i-1][j-num] | dp[i-1][j];
            }
        }
    }

    return dp[n-1][target];
};

optimization

考虑到在更新dp数组的状态的时候每次dp[i][j]都会以上一行作为参考进行状态转移，因此我们可以对于该数组进行空间优化,即将dp[n][target+1]修改为dp[target+1]，因此我们可以将空间复杂度由原来的O(n×target)O(n \times target)减少为O(target)O(target)。考虑到每一次更新状态时都要取上一行的状态，因此在更新状态时需要将j从大到小进行遍历。因为如果从小到大进行遍历的话，当计算dp[j]的状态是,dp[j-nums[i]]已经被更新过了，即被更新为第i行的数据，因此不可解。

1
2
3
4
5
6
7
8
for(let i=1;i<n;i++){
        let num = nums[i];
        for(let j=target;j>=num;j--){
            dp[j] |= dp[j-num];
        }
    }

    return dp[target];