# 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

``````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...

``````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];
}
};
``````

• why init bitset with size 5001 ?

• @zhoudayang2
The question says "Both the array size and each of the array element will not exceed 100", so the maximum possible sum is 10000 and so sum/2 <= 5000. Plus 1 to hold 0.

• Very Very Smart !!!

• @alvin-777 Thank yout! I know why I am confused with the size 5001, maybe the problem description have changed, which said "The array size will not exceed 200". so you should change your bitset size from 5001 to 10001?

• @alvin-777
This is absolutely brilliant and I have no clue how you came up with this solution.
Can you share some insights on your thinking process?

• @zhoudayang2 I see. I have modified my original post according to this change. It should be easier to read now. :)

• @soamaaazing It is difficult to explain how I came up with this idea. Usually it just flashed through my mind.
Though it's good to always try different ways to solve the same problem, like using a bitset instead of a bool vector.

• Can you explain more on this? Thanks

• @coder2 Maybe you can check out a normal dp solution using a bool vector (like this one) first.

• How to write in Java?

• brilliant solution!

• brilliant solution, I wouldn't claim the time complexity is O(n) though. Technically the bitset operation isn't O(1).

• Very concise solution! I see that the key loop of your solution `for (auto n : nums) bits |= bits << n;` seems to be the bit operation version of the N2 loop:

``````unordered_set<int> subsums;
for (auto n : nums) for (auto m : subsums) subsums.insert(n+m);
``````

Since your size of `bitset` is actually proportional to `MAX_ARRAY_SIZE = 200`, so would it also be O(N2) time? That is, is bit operation/assignment O(1) or also proportional to `bitset` size? Thanks.

• bits的第i位为1的话表示此数组里面存在组合使得该组合的和为i。
此处采用归纳法简单的分析下算法：
1.假设n之前的子列里面存在1~m,k~L……之间和的组合
2.填加了数字n之后，将会存在(1+n)~(m+n),(k+n)~(L+n)……之间和的组合（只要在上面的组合里面添加当前的元素n即可），在标记bits里面相当于将bits向左边移动n位，即bits << n
3.故目前为止，存在1~m,k~L……以及(1+n)~(m+n),(k+n)~(L+n)……之间和的组合
4.故bits |= bits << n

• This solution is quite amazing, thanks to Python's infinite-sized long integers, it is very easy to implement in Python

``````class Solution(object):

def canPartition(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
sum_val = 0
bits = 1
for num in nums:
sum_val += num
bits |= bits << num

return (not sum_val % 2 == 1) and (bits >> (sum_val // 2)) & 1 == 1
``````

It only takes 46 ms, while other DP solutions in Python take more than 600 ms.

Let me try to explain this solution a little bit. If I'm wrong, please correct me.

First, let me show you a normal DP solution,

``````class Solution(object):
def canPartition(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
sum_val = sum(nums)
if sum_val % 2 == 1:
return False
target = sum_val // 2
dp = [False] * (sum_val + 1)
dp[0] = True
for num in nums:
next_dp = [False] * (sum_val + 1)
for j in xrange(len(dp)):
if dp[j]:
next_dp[j + num] = True
next_dp[j] = True
dp = next_dp
return dp[target]
``````

`dp[j]` represents whether a specific sum value `j` can be gotten from (a subset of) `nums` or not. The basic idea is, if `dp[j]` is achievable, then `dp[i+num]` is achievable if we pick up the number `num`, and `dp[i]` is also achievable if we don't. I learnt this idea from https://discuss.leetcode.com/topic/76264/short-java-dp-solution-with-explanation

Let's get back to the solution with bitset. It replaces the `dp` table with a bitset, a bit `bits[j]` has the same meaning as `dp[j]`.

With the advantage of bitset, the inner loop of traversing `dp`, condition check of `dp[j]` and operations on `next_dp` are all transformed to bitwise shift operation, which is much more efficient.

A tiny example, `nums=[2, 3, 5]`, initial `bits` is `1`, traversing through `nums`

• when `num=2`, `bits=101`, which represents `nums` can sum to 0 and 2
• when `num=3`, `bits=101101`, which represents `nums` can sum to 0, 2, 3, 5
• when `num=5`, `bits=10110101101`, which represents `nums` can sum to 0, 2, 3, 5, 7, 8, 10

Finally, we just need to check if bits[5] is 0 or 1

• @alvin-777 This is sooooooo brilliant!!!!

• @alvin-777 said in Simple C++ 4-line solution using a bitset:
It's actually O(n^2), '<<' and '|' operators are not constant but O(n).
However it's still faster than bool vector.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.