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