题目：组合总和

  • 给定一个无重复元素的数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
  • candidates中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。 
示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]
示例 2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/combination-sum

分析：

回溯算法+栈，这是我的做法，看到很多算法高手的思路和方法都很棒，有用回溯的，有用dp的。

我放上两个比较好的题解:

思路：

  • 回溯算法一般都用递归来完成。最好的方法是画递归树。
  • 通过对每一层的递归，将所有等于target的答案全部都得到。

代码：

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        def recursion(cand, i):
            for j in range(i, len(candidates)):
                stack.append(candidates[j])
                res = candidates[j] + cand
                if res >= target:
                    if res == target:
                        ans.append(stack[:])
                    stack.pop()
                    continue
                else:
                    recursion(res, j)
                    stack.pop()
        for i in range(len(candidates)):
            stack = [candidates[i]]
            if candidates[i] < target:
                recursion(candidates[i], i)
            elif candidates[i] == target:
                ans.append(stack)
        return ans

复杂度分析：

  • 时间复杂度：O(n!) 个人认为
  • 空间复杂度：O(target) 个人认为target是主要影响答案数量的，当target变大时，最终返回的数量会非常多。