Python: 3 lines recursive

  • 0
    def canPartition(self, nums):
        def helper(nums, target):
            return not target if target <= 0 else any(helper(nums[i+1:], target - e) for i, e in enumerate(nums))
        return False if sum(nums) % 2 else helper(sorted(nums, reverse=True), sum(nums)//2)

    Same concept in a few more lines and easier to understand:

    def canPartition(self, nums):
        def helper(nums, j, target):
            if not target: return True
            if target < 0: return False
            return any(helper(nums, i+1, target - nums[i]) for i in range(j, len(nums)))
        msum = sum(nums)
        if msum % 2: return False
        return helper(sorted(nums, reverse=True), 0, msum//2)

Log in to reply

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