# AC Python solution, dfs

• The regular dfs solution will TLE. So I sort the array first, and search from thwo ends. This can optimize the time consuming a little bit.

``````class Solution(object):
def canPartitionKSubsets(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
if len(nums) < k or sum(nums) % k != 0 :
return False
sub_sum = sum(nums) / k
if any(num > sub_sum for num in nums):
return False
nums.sort()
return self.dfs(sub_sum,nums[-1], nums[: -1])

def dfs(self, sub_sum, cur_sum, nums):
if cur_sum == sub_sum:

if not nums:
return True
return self.dfs(sub_sum, nums[-1], nums[: -1])
size = len(nums)
for index in xrange(size):
tmp = nums[index]
if nums[index] + cur_sum <= sub_sum:
nums[index], nums[-1] = nums[-1], nums[index]
nums.pop()
if self.dfs(sub_sum, cur_sum + tmp, nums):
return True
nums.append(tmp)
nums[index], nums[-1] = nums[-1], nums[index]
return False
``````

• `if any(num > sub_sum for num in nums): return False`
Elements in nums are always positve?

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