题目：组合总和

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

来源：力扣（LeetCode）

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

分析：

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

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

思路：

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

代码：

  1. class Solution:
  2.     def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
  3.         ans = []
  4.         def recursion(cand, i):
  5.             for j in range(i, len(candidates)):
  6.                 stack.append(candidates[j])
  7.                 res = candidates[j] + cand
  8.                 if res >= target:
  9.                     if res == target:
  10.                         ans.append(stack[:])
  11.                     stack.pop()
  12.                     continue
  13.                 else:
  14.                     recursion(res, j)
  15.                     stack.pop()
  16.         for i in range(len(candidates)):
  17.             stack = [candidates[i]]
  18.             if candidates[i] < target:
  19.                 recursion(candidates[i], i)
  20.             elif candidates[i] == target:
  21.                 ans.append(stack)
  22.         return ans

复杂度分析：

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