Python 10 line bitwise O(n), no sorting


  • 0
    W

    This question is similar to coin change however the number of each kind of coin is limited.

    class Solution(object):
        def canPartition(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            s = sum(nums)
            if s == 0:
                return True
            if s % 2 == 0:
                s, current = s / 2, 0
                for num in nums:
                    current |= ((current or 1) << num) % (1 << (s + 1))
                    if current >= 1 << s:
                        return True
            return False
    

Log in to reply
 

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