class Solution:
# @param candidates, a list of integers
# @param target, integer
# @return a list of lists of integers
def combinationSum(self, candidates, target):
A=sorted(candidates)
stack=[[i] for i in A if i<target]
rst=[]
for i in A:
if i==target:
rst=[[i]]
break
while stack:
new_stack=[]
for i in stack:
for j in A:
if i[-1]>j:
continue
else:
crt_sum=sum(i+[j])
if crt_sum<target:
new_stack.append(i+[j])
elif crt_sum==target:
rst.append(i+[j])
stack=new_stack[:]
return rst
Friday, September 12, 2014
Leetcode: Combination Sum @Python
Subscribe to:
Post Comments
(
Atom
)
No comments :
Post a Comment