Friday, September 12, 2014

Leetcode: Combination Sum II @Python

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

No comments :

Post a Comment