I have a general solution to ksum with O(N^(k1)) complexity. The code returns correct results for sum3 and sum4. 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^(k1)).

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

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 k1 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.targetcur
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
"""