Clean Python DFS beats 90%


  • 2
    W

    dfs: ~90%

    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)

  • 1
    Z

    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!!


  • 0
    W

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


  • 0
    Z

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

    I appreciate that you can share your analysis about the time complexity of your solution.

    Thanks!!


Log in to reply
 

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