Friday, September 12, 2014

Leetcode: Combination Sum @Python

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

No comments :

Post a Comment