代码献上：
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
#对数组进行排序，最小值 > target的话，则return back
#组合情况：
candidates.sort() #对数组进行排序
if candidates[0] > target :
return []
else:
ans = []
#出现重复元素
def ret(s,array,remain):
for i in range(s,len(candidates)):
c = candidates[i]
if remain == c:
ans.append(array + [c])
elif(remain > c):
ret(i,array + [c],remain - c)
else:
return []
ret(0,[],target)
return ans
本题主要用到一种回溯算法的思想，接下来简要介绍一下回溯算法。
回溯法，又名试探法，是一种优选搜索算法，可以理解为试探性搜索算法。在搜索到某一步的时候，如果发现不能满足条件，那么就退回到上一步，在上一步重新选择。
回溯法是以深度优先方式来搜索问题的解，也就是里面的每一步可以理解为一个结点，这些步骤串起来就是一棵树，也就是解空间树。比如第一步只有 1 种做法，第二步有 4 种做法，那么第二步选择一种尝试之后，如果匹配，会假设当前步骤没有问题，继续往第 3 步深入探索，而不是先尝试第二步的其他选择。
当搜索解空间树中的任何一个结点的时候，判断该结点是不是包含问题的解。
如果不包含，那么就把当前的结点以及剩下的节点步骤全部抛弃（也称为剪枝），然后往上一层的结点回溯，也就是退回上一步重新选择（之前的选择走不通）。
如果包含，说明当前结点是可能获取到解的，继续进入下一层子树进行深度优先搜索。
一般来说，回溯法可以有两种做法：
递归：设计思路比较简单，但效率不高。
递推：算法设计相对比较复杂，但效率高。
类似的题目还有：
八皇后问题（待更新）机器走迷宫（待更新）0-1背包（待更新）旅行售货员问题（待更新）图的m着色问题（待更新）
