# 【进阶篇 - Day 49】 2020-12-19 - 39. 组合总和（03. 剪枝 ）
# 题目描述
# 入选理由
- 熟悉了剪枝的形象化，接下来开始真正的剪枝
- 回溯的题目基本都需要剪枝，这是回溯的一个考点
# 题目描述
给定一个无重复元素的数组 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] ]
提示：
1 <= candidates.length <= 30 1 <= candidates[i] <= 200 candidate 中的每个元素都是独一无二的。 1 <= target <= 500
来源：力扣（LeetCode） 链接：leetcode-cn.com/problems/combination-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
# 我的回答
https://github.com/leetcode-pp/91alg-2/issues/79#issuecomment-748729900
# 解法一
# 时空复杂度
时间复杂度：O(n^2) 回溯的复杂度怎么分析啊
空间复杂度: O(n)
好气 滴滴面试考到了，早刷几天就好了，我还在那跟他扯动态规划 ，凉凉
var combinationSum = function (candidates, target) {
let res = []
function dfs(index, temp = [], sum = 0) {
if (sum === target) res.push([...temp])
if (sum > target) return
for (let i = index; i < candidates.length; i++) {
temp.push(candidates[i])
dfs(i, temp, sum + candidates[i])
temp.pop()
}
}
dfs(0)
return res
};