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=*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)
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.
@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.
What's the time complexity of your solution?
I made a rough analysis of the time complexity:
Overall time complexity =
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 =
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.
I appreciate that you can share your analysis about the time complexity of your solution.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.