Simple C++ 4-line solution using a bitset


  • 35
    A

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

  • 0
    Z

    why init bitset with size 5001 ?


  • 0
    A

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


  • 0

    Very Very Smart !!!


  • 0
    Z

    @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?


  • 0

    @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?


  • 0
    A

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


  • 0
    A

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


  • 0
    C

    Can you explain more on this? Thanks


  • 0
    A

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


  • 0

    How to write in Java?


  • 0
    Z

    brilliant solution!


  • 0

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


  • 0
    C

  • 0

    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.


  • 5
    S

    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


  • 3
    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


  • 0
    G

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


Log in to reply
 

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