7 Lines 59ms Recursive Python Solution


  • 6

    Seek whether there's a combination has the sum equal to half of total sum.
    Simply return False if sum of the list is not even.
    Target minus each element as Target for next recursion of the rest elements.

    Base case:
    Target < 0 (ignore)
    Target == 0 (return True)

    Recursive case:
    Otherwise

    class Solution(object):
        def canPartition(self, nums):
            nums.sort(reverse=True)
            def helper(start, target):         # Here path is not needed
                if target < 0: return
                elif target == 0: return True
                for i in xrange(start, len(nums)):
                    if helper(i+1, target-nums[i]): return True
                return False
    
            return False if sum(nums)%2 else helper(0, sum(nums)/2)
    

    EDIT:
    modified based on @WKVictor 's advise.

    EDIT 2:
    Thanks @whglamrock 's advise, added one line for new test case. => nums.sort(reverse = True)


  • 1
    W

    Nice backtracking solution. But I do not think you need the variable path.


  • 0

    @WKVictor You're brilliantly right. Thanks for your kindly advise!


  • 1
    W

    @YJL1228

    Your solution got TLE for test case:
    [1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,100,99,100]

    The Admin probably added few test cases yesterday so typical DFS solution might not work.


  • 0

    @whglamrock Thanks for your advise. New test cases can be solved by additional one line.


  • 0
    Z

    @YJL1228 I am wondering why it can pass the test by sorting the ''' nums''' reversely? I had my own DFS solution, it could not pass the test, but after adding '''nums.sort(reverse=True) ''', then it worked.


  • 0
    I

    @Zhuangkun said in 7 Lines 59ms Recursive Python Solution:

    @YJL1228 I am wondering why it can pass the test by sorting the ''' nums''' reversely? I had my own DFS solution, it could not pass the test, but after adding '''nums.sort(reverse=True) ''', then it worked.

    I think this is just a hack for this specific sequence.


  • 0
    M

    @YJL1228 I probably din't understand the question, but why did you do this:

    return False if sum(nums)%2
    

    If sum is even, return False? Why? What about: [2,4,6]


  • 0

    @modqhx the line you've highlighted is asking: if the sum is odd, return False. if the sum is even, the if condition will be False, then won't return False.


  • 0

    @YJL1228 Nice recursive solution! I have a similar one here but without sorting.

    Could you comment what is the sorting for? (I was thinking maybe sorting could speed up the DFS, but the subsum does not seem to be searched faster if adding smaller or larger number first. And is it necessary to use the recursive calls in a loop? Thanks.


  • 1

    @zzg_zzm Thanks for your reply. Sure, without sorting this solution will get TLE, and I'm not sure the limitation between different language, but the idea is as follows:
    If the answer is True, (two partition, their partial sums both equal to half of sum), then the partition having fewer numbers will be more desired then the other. For example, [100, 1, 1, 1, 1, 1, 1, .....,1 ,1], subset {100} is more desired than {1}*100.
    All above can be summarized into this assumption: The average number in desired partition must be larger.
    The sorting is simply put larger numbers first, in order to get this kind of partition as fast as possible.
    I "guess" the recursive calls in a loop is not a must, but implementing other algorithm might be easier than optimizing this one. I think your own solution, like plenty other solutions in the fourm, is way better than mine : )


  • 1

    @YJL1228 Thanks for the comment on the sorting! So, it is the "if you want to fail, make sure to fail quickly". And traversing through larger numbers indeed first help to speed up.

    Now I have tested and found that DFS without sorting should always get TLE and OJ's test cases are incomplete.

    My original code using reverse_iterator to traverse through tail to head happens to favor the following test case from OJ:
    [1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,100,99,100]
    which has larger values near the tail. But I tested to use a test case by reversing the array or simply use forward iterator, the code will get TLE. So the DFS without sorting is just lucky to get through all existing test cases since the long descending array is not included for the tests. I have also added sort to my original code for robustness. Actually I favor DFS over DP because DP makes excessive dp[i][j] entries calculations which might not be needed.

    @administrators I suggest to add the same long array but with order reversed. Also, another extreme test case (if not included yet) is to have a constant array of huge size (odd and even) to make sure DFS solution will go through half of the numbers to test the maximum time limit.


  • 0

    @zzg_zzm Done. I have added the test case with it reversed.


  • 0

    @1337c0d3r Thank you very much!


  • 0
    Z

    @YJL1228

    could just do something like this, but indeed, sorting would double the speed.

    class Solution(object):
        def canPartition(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            total = sum(nums)
            # nums.sort(reverse=True)
            if total & 1:
                return False
            self.cache = {}
            half = total / 2
            nums.sort()
            return self.helper(nums, 0, half)
            
        def helper(self, nums, i, total):
            if (i, total) in self.cache:
                return self.cache[(i, total)]
            if i == len(nums) or total < 0:
                return False
            if total == 0:
                return True
            for idx in xrange(i, len(nums)):
                if self.helper(nums, idx + 1, total - nums[idx]):
                    return True
            self.cache[(i, total)] = False
            return False
    

  • 0
    Z

    @zzg_zzm by the way, I just copied the solution in this post and get timeout even with sorting, it seems like they have fixed their test cases. definitely need memorization here.


  • 6
    Z

    Seems like the code can't pass OJ due to TLE, I think they have changed their test cases. Here is an updated version

    
    class Solution(object):
        def canPartition(self, nums):
            cache = {}
            def helper(start, target):         # Here path is not needed
                if (start, target) in cache:
                    return cache[(start, target)]
                if target < 0:
                    return
                elif target == 0:
                    return True
                for i in xrange(start, len(nums)):
                    if helper(i+1, target-nums[i]):
                        return True
                cache[(start, target)] = False
                return False
            return False if sum(nums)%2 else helper(0, sum(nums)/2)
    

  • 0

    @zzg_zzm said in 7 Lines 59ms Recursive Python Solution:

    Actually I favor DFS over DP because DP makes excessive dp[i][j] entries calculations which might not be needed.

    DP doesn't necessarily need to be 2-dimension like dp[i][j].
    1 dimension can do it all.

        def canPartition(self, nums):
            def helper(start, target):  
                dp = [True] + [False] * target
                for i in xrange(len(nums)):
                    for j in xrange(target, nums[i] - 1, -1):
                        dp[j] = dp[j] or dp[j - nums[i]]
                        if j == target and dp[j]:
                            return True
                return False
            return False if sum(nums) % 2 else helper(0, sum(nums) / 2)

  • 0
    S

    @YJL1228 said in 7 Lines 59ms Recursive Python Solution:

    class Solution(object):
    def canPartition(self, nums):
    nums.sort(reverse=True)
    def helper(start, target): # Here path is not needed
    if target < 0: return
    elif target == 0: return True
    for i in xrange(start, len(nums)):
    if helper(i+1, target-nums[i]): return True
    return False

        return False if sum(nums)%2 else helper(0, sum(nums)/2)
    

    It gets TLE for
    [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,100]
    I guess they keep adding cases to fail this method...


  • 0
    J

    @zhongyuan9817 Excellent solution with memorization to cut down the search space!


Log in to reply
 

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