示例:1：

输入: candidates = [2, 3, 6, 7]，target = 7，所求解集为: [[7], [2, 2, 3]]

示例2：

输入：candidates = [2, 3, 6, 7]， depth=3,所求解集为：[[2,3,6],[2,3,7],[2,6,7],[3,6,7]]

示例3：

输入：candicates=[a,b,c,d],求全排列

 

思路：

构建一个树

 

     *

/  |   |   \

2 3  6   7

|　　　　　　\

(2,3,6,7)　　(2,3,6,7)

每一层为选择的数，层的元素为满足条件的candicates,每次递归为选择一个数. 利用先序遍历，入栈出站进行全遍历

根据条件决定终止条件。放入结果集,返回

如示例2：

def dfs(result,path,start,k,candicates):

　　if depth ==3:

　　　　result.append(path[:])

　　　　return;

　　for i in range(start,len(candicates)):

　　　　path.append(candicate[i])

　　　　dfs(result,path,i,k,candicates): # i 是含有重复的，i+1不含有重复的

　　　　path.pop()

例code:

　示例2：

class Solution:
    def sumisprime(self,A,k):
        result = []
        path = []
        start = 0
        if len(A)==0:
            return []
        self.dfs(result,path,start,A,k)
        return result

    def dfs(self,list, path, start, A, k):
        if len(path)==k:
            list.append(path[:])
            return
        for i in range(start,len(A)):
            path.append(A[i])
            self.dfs(list,path,i+1,A,k)
            path.pop()

if __name__=='__main__':
    solution=Solution()
    print(solution.sumisprime([3,7,12,19],3))

示例1：（from leetcode力扣 https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/ ）

from typing import List

class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
　　size = len(candidates)
　　if size == 0:
　　　　return []

# 剪枝的前提是数组元素排序
# 深度深的边不能比深度浅的边还小
# 要排序的理由：1、前面用过的数后面不能再用；2、下一层边上的数不能小于上一层边上的数。
　　candidates.sort()
# 在遍历的过程中记录路径，一般而言它是一个栈
　　path = []
　　res = []
# 注意要传入 size ，在 range 中， size 取不到
　　self.__dfs(candidates, 0, size, path, res, target)
　　return res

def __dfs(self, candidates, begin, size, path, res, target):
# 先写递归终止的情况
if target == 0:
# Python 中可变对象是引用传递，因此需要将当前 path 里的值拷贝出来
# 或者使用 path.copy()
　　res.append(path[:])

　　for index in range(begin, size):
　　　　residue = target - candidates[index]
// “剪枝”操作，不必递归到下一层，并且后面的分支也不必执行
　　　　if residue < 0:
　　　　　　break
　　path.append(candidates[index])
# 因为下一层不能比上一层还小，起始索引还从 index 开始
　　self.__dfs(candidates, index, size, path, res, residue)
　　path.pop()

if __name__ == '__main__':
　　candidates = [2, 3, 6, 7]
　　target = 7
　　solution = Solution()
　　result = solution.combinationSum(candidates, target)
　　print(result)。