# Instead of remember all sums, this dfs only remember one sum

``````class Solution(object):
def canPartitionKSubsets(self, nums, k):
if k==1: return True

self.n=len(nums)
if k>self.n: return False

total=sum(nums)
if total%k: return False

self.target=total/k
visit=[0]*self.n

nums.sort(reverse=True)
def dfs(k,ind,sum,cnt):
if k==1: return True
if sum==self.target and cnt>0:
return dfs(k-1,0,0,0)
for i in range(ind,self.n):
if not visit[i] and sum+nums[i]<=self.target:
visit[i]=1
if dfs(k,i+1,sum+nums[i],cnt+1):
return True
visit[i]=0
return False

return dfs(k,0,0,0)``````

• Hi,

I tried to remove the `cnt`, it also can pass the leetcode, but the performance is lower than your current implementation. May I know why using `cnt` can boost performance? It seems that there is no scenario will meet that `sum == self.target and cnt == 0`.

Thanks!!

• @zproject89 let's say the target==0, I put cnt>0 here is to avoid the corner case where the sum of an empty array is also 0.

• @weidairpi Thanks for the response. OK, I see your point. It makes sense. The interesting thing is that if I remove the `cnt`, leetcode shows the performance beats 57%. If there is `cnt`, the performance beats 97%. Huge difference! Before I wonder whether there is some very tricky stuff which the `cnt` brings in.

Another question:
What's the time complexity of your solution?
I made a rough analysis of the time complexity:
Overall time complexity = `O(k*n!)`.
Because to build each bucket, the first level recursion has `n` options, the second level has `n - 1` options, the third level has `n - 2` options, `.....` So to build one bucket takes `O(n!)` time complexity, and there are k buckets, the overall time complexity = `O(k*n!)`.

But the real time complexity must be more tight than the above. Because the element used by one bucket will not be re-used by another.