Recursive DFS accepted - try unique nums only


  • 0
    Y

    Count the frequency of nums, Try to make sum(nums)//2 (if even). For each unique num, subtract it from target and decrement its count in the frequency map then recurse. Increment frequency map if no solution found. This avoids duplication e.g. in the test case where there are many 1s.
    Might well be faster if dictionary was ordered from largest key first.

    from collections import Counter
    
    class Solution(object):
        def canPartition(self, nums):
            nums_sum = sum(nums)
            if nums_sum % 2 == 1:
                return False
    
            freq = Counter(nums)
            return self.partition(freq, nums_sum // 2)
    
        def partition(self, freq, target):
            if target == 0:
                return True
            if target < 0:
                return False
    
            for num in freq:
                if freq[num] == 0:
                    continue
                freq[num] -= 1
                if self.partition(freq, target - num):
                    return True
                freq[num] += 1
    
            return False

Log in to reply
 

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