要求
- 非空数组的所有数字都是正整数,是否可以将这个数组的元素分成两部分,使得每部分的数字和相等
- 最多200个数字,每个数字最大为100
示例
- [1,5,11,5],返回 true
- [1,2,3,5],返回 false
思路
- 在n个物品中选出一定物品,填满sum/2的背包
- 状态:F(n,C)
- 转移:F(i,c)=F(i-1,c) || F(i-1,c-w(i))
- 复杂度:O(n*sum/2) = O(n*sum)
实现
递归+记忆化搜索(归纳法)
- 16-17:是否计算过
1 class Solution {
2 private:
3 // memo[i][c]表示用索引为[0...i]的元素,是否可以完全填充一个容量为c的背包
4 // -1表示未计算,0表示不可填充,1表示可填充
5 vector<vector<int>> memo;
6
7 // 使用nums[0...index],是否可以完全填充一个容量为sum的背包
8 bool tryPartition(const vector<int> &nums, int index, int sum){
9
10 if( sum == 0 )
11 return true;
12
13 if( sum < 0 || index < 0 )
14 return false;
15
16 if( memo[index][sum] != -1 )
17 return memo[index][sum] == 1;
18
19 memo[index][sum] = ( tryPartition(nums, index-1, sum ) ||
20 tryPartition(nums, index-1, sum-nums[index] ) ) ? 1 : 0;
21 return memo[index][sum] == 1;
22 }
23 public:
24 bool canPartition(vector<int>& nums) {
25 int sum = 0 ;
26 for( int i = 0 ; i < nums.size() ; i ++ ){
27 assert( nums[i] > 0 );
28 sum += nums[i];
29 }
30
31 if( sum%2 != 0 )
32 return false;
33
34 memo = vector<vector<int>>( nums.size(), vector<int>(sum/2+1,-1));
35 return tryPartition( nums, nums.size()-1, sum/2 );
36 }
37 };
动态规划(演绎法)
- 采用优化方式,memo为一维数组
1 class Solution {
2
3 public:
4 bool canPartition(vector<int>& nums) {
5 int sum = 0 ;
6 for( int i = 0 ; i < nums.size() ; i ++ ){
7 assert( nums[i] > 0 );
8 sum += nums[i];
9 }
10
11 if( sum%2 != 0 )
12 return false;
13
14 int n = nums.size();
15 int C = sum/2;
16 vector<bool> memo(C+1, false);
17
18 for( int i = 0 ; i <= C ; i ++ )
19 memo[i] = ( nums[0] == i );
20
21 for( int i = 1 ; i < n ; i ++ )
22 for( int j = C ; j >= nums[i] ; j -- )
23 memo[j] = memo[j] || memo[j-nums[i]];
24
25 return memo[C];
26 }
27 };
相关
- 322 Coin Change
- 377 Combination Sum IV
- 474 Ones and Zeros
- 139 Word Break
- 494 Target Sum