# 7 Lines 59ms Recursive Python Solution

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

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

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

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

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

• @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]`

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

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

• @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 : )

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

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

• @1337c0d3r Thank you very much!

• @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
``````

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

• 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)
``````

• 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)``````

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

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

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