[刷题] 416 Partition Equal Subset Sum

要求

非空数组的所有数字都是正整数，是否可以将这个数组的元素分成两部分，使得每部分的数字和相等
最多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 };

View Code

动态规划（演绎法）

采用优化方式，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 };

View Code