416. Partition Equal Subset Sum

  • 38.3%

https://leetcode.com/problems/partition-equal-subset-sum/?tab=Description

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

  1. Each of the array element will not exceed 100.
  2. The array size will not exceed 200.
1
2
3
4
5
6
7
Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].
1
2
3
4
5
6
7
Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

相似问题 494

方法一:

两类,A + B = sum, A - B = 0得知 A=B = sum/2,sum必须为偶数

建立一个大vector然后去遍历,遍历方法可以学习一下

我的代码实现:

其中值得学习的,一个是accumulate函数,一个是遍历的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
bool canPartition(vector<int>& nums) {
int s = accumulate(nums.begin(), nums.end(), 0);
return s&1 ? false : helper(s>>1, nums);
}

bool helper(int s, vector<int>& nums){
vector<bool>dp(s+1, false);
dp[0] = true;
for(auto num:nums)
for(int i=s; i>=num; i--)
dp[i] = dp[i] || dp[i-num];
return dp[s];
}
};

方法二:

值得学习的地方,一个是bitset库,一个是根据题目给定的最大值,设定最长的一个bitset,还有就是每次一个数字,我们都使用bitset<<n,这样的方法非常神奇。

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
bool canPartition(vector<int>& nums) {
int s = accumulate(nums.begin(), nums.end(), 0);
if(s&1)
return false;
bitset<20001> bits;
bits[0] = 1;
for(auto num:nums)
bits |= bits<<num;
return bits[s>>1];
}
};

https://discuss.leetcode.com/topic/62334/simple-c-4-line-solution-using-a-bitset

Simple C++ 4-line solution using a bitset
Note: as @zhoudayang2 pointed out, the question description has changed (max array size 100 ==> 200). I have modified my code below according to the new description, and also made it a bit easier to understand.

Time complexity O(n), size of the bitset is 1256 bytes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
bool canPartition(vector<int>& nums) {
const int MAX_NUM = 100;
const int MAX_ARRAY_SIZE = 200;
bitset<MAX_NUM * MAX_ARRAY_SIZE / 2 + 1> bits(1);
int sum = 0;
for (auto n : nums) {
sum += n;
bits |= bits << n;
}
return !(sum % 2) && bits[sum / 2];
}
};

It’s possible to shorten the solution to 4 lines, by using std::accumulate(), but that doesn’t really make you type less or make it run faster though…

1
2
3
4
5
6
7
8
9
class Solution {
public:
bool canPartition(vector<int>& nums) {
bitset<10001> bits(1);
int sum = accumulate(nums.begin(), nums.end(), 0);
for (auto n : nums) bits |= bits << n;
return !(sum & 1) && bits[sum >> 1];
}
};

https://discuss.leetcode.com/topic/62285/concise-c-solution-summary-with-dfs-dp-bit

Concise C++ Solution summary with DFS, DP, BIT

DFS solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
bool backtrack(vector<int>& nums, int start, int target) {
if (target <= 0) return target == 0;
for (int i = start; i < nums.size(); i++)
if (backtrack(nums, i + 1, target - nums[i])) return true;
return false;
}

bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
return !(sum & 1) && backtrack(nums, 0, sum >> 1);
}
};

DFS can’t pass the OJ, as more test cases are added. So here comes a DP solution based on @Hermits solution

1
2
3
4
5
6
7
8
9
10
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0), target = sum >> 1;
if (sum & 1) return false;
vector<int> dp(target + 1, 0);
dp[0] = 1;
for(auto num : nums)
for(int i = target; i >= num; i--)
dp[i] = dp[i] || dp[i - num];
return dp[target];
}

A very fast and cool Bit solution by @alvin-777 solution

1
2
3
4
5
6
bool canPartition(vector<int>& nums) {
bitset<5001> bits(1);
int sum = accumulate(nums.begin(), nums.end(), 0);
for (auto n : nums) bits |= bits << n;
return !(sum & 1) && bits[sum >> 1];
}

https://discuss.leetcode.com/topic/63049/my-simple-c-dp-code-with-comments

My Simple C++ DP Code with Comments

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum & 1) return false;
int half = sum >> 1;

vector<bool> accessibility(half + 1, false);
accessibility[0] = true; // '0' is always reachable
//For all num in nums, check the accessibility from half - num to 0.
//If 'i' is accessible by former numbers, then 'i + num' is also accessible. (DP Algorithm)
for(auto num : nums)
//Below here we must start from 'half' downto 'num', otherwise current 'num' might be multiply used.
//e.g.: If num == 2, then we will have 2, 4, 6... will all be accessible and lead to wrong answer.
for(int i = half; i >= num; i--){
if (accessibility[i - num] == true){
accessibility[i] = true;
}
}
return accessibility[half];
}
};

python


https://discuss.leetcode.com/topic/62308/7-lines-59ms-recursive-python-solution

7 Lines 59ms Recursive Python Solution

Seek whether there’s a combination has the sum equal to half of total sum.

Simply return False if sum of the list is not even.

Target minus each element as Target for next recursion of the rest elements.

Base case:

Target < 0 (ignore)

Target == 0 (return True)

Recursive case:

Otherwise

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def canPartition(self, nums):
nums.sort(reverse=True)
def helper(start, target): # Here path is not needed
if target < 0: return
elif target == 0: return True
for i in xrange(start, len(nums)):
if helper(i+1, target-nums[i]): return True
return False

return False if sum(nums)%2 else helper(0, sum(nums)/2)

https://discuss.leetcode.com/topic/64124/4-line-passed-python-solution

4 line passed python solution

1
2
3
4
5
6
7
8
9
10
class Solution(object):
def canPartition(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
possible_sums = {0}
for n in nums:
possible_sums.update({(v + n) for v in possible_sums})
return (sum(nums) / 2.) in possible_sums

java


33ms, , October 18, 2016

https://discuss.leetcode.com/topic/62312/java-solution-similar-to-backpack-problem-easy-to-understand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
public boolean canPartition(int[] nums) {
if(nums == null || nums.length == 0)
return true;

int volumn = 0;
for(int num:nums)
volumn += num;

if(volumn % 2 != 0)
return false;

volumn /= 2;

boolean[] dp = new boolean[volumn + 1];
dp[0] = true;
for(int i=1; i<=nums.length; i++)
for(int j=volumn; j>=nums[i-1]; j--)
dp[j] = dp[j] || dp[j-nums[i-1]];

return dp[volumn];
}
}
谢谢你,可爱的朋友。