js.39. 组合总和

链接：39. 组合总和

题目：

给你一个无重复元素的整数数组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输出:[]

提示：

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• candidates的所有元素互不相同
• 1 <= target <= 40

思路：

利用回溯的思想来解决这道题。

我的想法是把每次遍历过的数字放在overlist中保存，

然后去递归。combinationSum(candidates.slice(i), target - candidates[i], [...overList])

代码：

/** * @param {number[]} candidates * @param {number} target * @return {number[][]} */ var combinationSum = function(candidates, target, overList = []) { let result = []; candidates.sort((a,b)=>a-b); for (let i = 0; i < candidates.length; i++) { if(candidates[i] > target) { continue; }else if(candidates[i] == target) { target = target - candidates[i]; overList.push(candidates[i]); break; } overList.push(candidates[i]) let temp = combinationSum(candidates.slice(i), target - candidates[i], [...overList]); result.push(...temp); overList.pop(); } if(target == 0) result.push(overList); return result; };

题解：

var combinationSum = function(candidates, target) { const ans = []; const dfs = (target, combine, idx) => { if (idx === candidates.length) { return; } if (target === 0) { ans.push(combine); return; } // 直接跳过 dfs(target, combine, idx + 1); // 选择当前数 if (target - candidates[idx] >= 0) { dfs(target - candidates[idx], [...combine, candidates[idx]], idx); } } dfs(target, [], 0); return ans; };