A simple general solution to k-sum with O(N^(k-1)) complexity


  • 0
    W

    I have a general solution to k-sum with O(N^(k-1)) complexity. The code returns correct results for sum-3 and sum-4. But %=% the trouble is it exceed time limit for the last long input.

    Can anyone help out? Thank you so much in advance!

    The idea is very simple: 1) simply use DFS, the complexity would be O(N^k); 2) Together with a dictionary trick, the complexity can be O(N^(k-1)).

    1. A naive approach is to DFS to search for possible k subarray such that their sum is 0 or target. Since the depth of the tree is k, the complexity would be O(N^k).

    2. To reduce the complexity, we can use a dictionary to remember what numbers “nums” contains and record the number of times they appear in "nums". Then, at the k-1 level of tree, we don't need to go one step deeper. If the sum of numbers along the path is current, we can just check if there is any number in the dictionary such that it is equal to -current. Here we need to be careful. To avoid duplications,
      we need to check if the number of times -current appear along the path is less than the number of time it appear in "nums".

    I think this simple idea can solve a lot of similar problems, but I get the Time Exceeding Limit error for large input.

    I really appreciate if anyone can point out the mistake!
    """
    class Solution(object):
    def threeSum(self, nums):

        self.res=[]
        self.num=nums
        #self.num.sort()
        self.D={}
        self.dic={}
        self.target=0
        for i in range(len(self.num)):
            if self.dic.has_key(self.num[i])==False:
                self.dic[self.num[i]]=1
            else:
                self.dic[self.num[i]]+=1
        
        self.dfs([],[],0)
        return self.res
    
    def dfs(self,path,L,cur):
        
        if len(path)==0:
            st=0
        elif path[len(path)-1]<len(self.num)-1:
            st=path[len(path)-1]+1
        else:
            return
        if len(path)<=1:
            for i in range(st,len(self.num)):
                path.append(i)
                L.append(self.num[i])
                L_tem=sorted(L)
                if self.D.has_key(tuple(L_tem))==False:
                    self.D[tuple(L_tem)]=1
                    self.dfs(path,L,cur+self.num[i])
                path.pop()
                L.pop()
                
        elif len(path)==2:
            
            last=self.target-cur
            if self.dic.has_key(last)==False:
                return
            else:
                count=0
                for i in range(len(path)):
                    if L[i]==last:
                        count+=1     
                if count<self.dic[last]:
                    L_tem=sorted(L+[last])
                    if self.D.has_key(tuple(L_tem))==False:
                        self.res.append(L_tem)
                        self.D[tuple(L_tem)]=1
                        return
        return
    

    """


Log in to reply
 

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