# Python Backtracking without TLE,easy to understand

• The key points to avoid TLE, 1. reverse sort the array, to check the biggest number first, 2. if any single num is great than the average, return false immediately

``````    def canPartitionKSubsets(self, A, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
def dfs(A,target,step,num,k):
if step==k-1:         # if previous k-1 subset has the average value, then the sum of the rest must be the average
return True
n=len(A)
for i in xrange(n):
B=A[:i]+A[i+1:]
if num+A[i]==target:
if dfs(B,target,step+1,0,k):  # if sum of previous number and current number is the average, the step plus 1,
return True
elif num+A[i]<target:
if dfs(B,target,step,num+A[i],k):
return True
elif num==0: return False  #if any single num is great than the average, return false immediately
return False

n,total=len(A),sum(A)
if total%k!=0: return False
target=total/k
A.sort(reverse=True)     # reverse  sort to check bigest number first
res=dfs(A,target,0,0,k)
return res``````

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