Problem
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:
- All numbers (including
target) will be positive integers. - The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [2,3,6,7], target = 7, A solution set is: [ [7], [2,2,3] ] Example 2:
Input: candidates = [2,3,5], target = 8, A solution set is: [ [2,2,2,2], [2,3,3], [3,5] ] Solution
/** * @param {number[]} candidates * @param {number} target * @return {number[][]} */ var combinationSum = function(candidates, target) { var res = []; var len = candidates.length; candidates.sort((a, b) => (a - b)); dfs(res, [], 0, len, candidates, target); return res; }; var dfs = function (res, stack, index, len, candidates, target) { var tmp = null; if (target < 0) return; if (target === 0) return res.push(stack); for (var i = index; i < len; i++) { if (candidates[i] > target) break; tmp = Array.from(stack); tmp.push(candidates[i]); dfs(res, tmp, i, len, candidates, target - candidates[i]); } }; Explain:
对树进行深度优先的搜索。注意解法不能重复，即下次搜索从 index 开始
Complexity:
- Time complexity : O(n^2).
- Space complexity : O(n^2).