class Solution:
# @param candidates, a list of integers
# @param target, integer
# @return a list of lists of integers
def combinationSum2(self, candidates, target):
A=sorted(candidates)
n=len(A)
stack=[([A[i]],i,A[i]) for i in range(n) if A[i]<target]
rst=[]
for i in A:
if i==target:
rst=[[i]]
break
while stack:
new_stack=[]
for i in stack:
for j in range(i[1]+1,n):
crt_sum=i[2]+A[j]
if crt_sum<target:
new_stack.append((i[0]+[A[j]],j,crt_sum))
elif crt_sum==target and (i[0]+[A[j]] not in rst):
rst.append(i[0]+[A[j]])
stack=new_stack[:]
return rst
Friday, September 12, 2014
Leetcode: Combination Sum II @Python
Subscribe to:
Post Comments
(
Atom
)
No comments :
Post a Comment