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[i1][j]dp[i1][j]dp[i1][jnums[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];