39. Combination Sum

题目

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[
[7],
[2, 2, 3]
]

题意

给定一个set集，给定一个目标值target，从set集中选取元素，set集中的元素可以重复选取，组成一个列表，使得列表中的元素和为target，找出所有满足条件的列表集

思路

这种问题是重复性的问题，有通项公式，而且需要放在循环中遍历所有元素:

result,res,out=self.digui(i,res,out,target,candidates,result)

比如上面的示例，
记res为列表，out为结果
初始条件是： res=[]，out=0，candidates=[2，3，6，7]，i=0
第一次调用，判断out+candidates[i]<target，则将第i个元素加入，此时传参结果为：res=[2],out=2,candidates[2,3,6,7],i=0
继续调用，判断，直到不满足条件，出栈，跳出当层递归，增加i，继续

python实现

class Solution(object):
    
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        result = []
        res=[]
        out=0
        index=-1
        candidates=sorted(candidates)
        result,res,out=self.digui(0,res,out,target,candidates,result)
        return result

    def digui(self,i,res,out,target,candidates,result):
        while i<len(candidates):
            if out+candidates[i]>=target:
                if out+candidates[i]==target:
                    temp = [k for k in res]
                    temp.append(candidates[i])
                    result.append(temp)
                if len(res)>0:
                    out -= res[-1]
                    res.pop(-1)
                return result,res,out
            else:
                out+=candidates[i]
                res.append(candidates[i])
                result,res,out=self.digui(i,res,out,target,candidates,result)
                i+=1
        if len(res)>0:
            out-=res[-1]
            res.pop(-1)
        return result,res,out

这个解法在leetcode上运行速度上超过了95%accepted的代码