算法题-03

组合总数

给你一个无重复元素的整数数组candidates和一个目标整数target，找出candidates中可以使数字和为目标数target的 所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。

candidates中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为target的不同组合数少于150个。

示例 1：

输入：candidates = [2,3,6,7], target = 7输出：[[2,2,3],[7]]解释：2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选， 7 = 7 。 仅有这两种组合。

示例 2：

输入:candidates = [2,3,5], target = 8输出:[[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入:candidates = [2], target = 1输出:[]

/** * @param {number[]} candidates * @param {number} target * @return {number[][]} */ var combinationSum = function(candidates, target) { const path = [] const res = [] const backtrack = (startIndex,sum) => { if(sum === target){ res.push([...path]) return } if(sum > target){ return } for(let i = startIndex; i < candidates.length;i++){ const cur = candidates[i] path.push(cur) backtrack(i,sum + cur) path.pop() } } backtrack(0,0) return res };

首先用一个数组path存当前的组合

用一个变量sum记录当前和

从某个起始下标开始选数，由于题目告诉我们同一个数字可以无限制重复被选取，且如果被选取的数量相同则组合是相同的，所以我们要避免出现[2,2,3]，[3,2,2]同时存在的情况，可以通过后面的递归只能从当前的下表选取从而避免这一情况，

2 → 只能选 2、3、6、7 3 → 只能选 3、6、7

在回溯函数中，注意这么几块

1. 终止条件：和正好等于 target

if (sum === target) { res.push([...path]) // 注意要拷贝 return }

. 2.剪枝：和超过 target，直接返回，这里主要目的的效率提升

if (sum > target) { return }

3. 遍历候选数组

for (let i = startIndex; i < candidates.length; i++) { const cur = candidates[i] // 选择 path.push(cur) // 递归：i 而不是 i+1（允许重复使用） backtrack(i, sum + cur) // 撤销选择（回溯） path.pop() }

注意：

因为数字可以重复使用，backtrack(i, sum + cur)，如果写成i + 1，就变成每个数只能用一次了

res.push([...path])，因为path是同一个数组对象，不拷贝的话，后面回溯会把结果全改掉