题目描述
给定一个无重复元素的数组 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]
]
来源：LeetCode
思路
深度优先搜索。每次记录当前和，当前搜索到的下标，和当前使用数字。若当前和等于target，则找到一个组合。
解法
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
const combinationSum = (candidates, target) => {
const result = [];
const dfs = (value, index, nums) => {
if (index >= candidates.length || value > target) return;
if (value === target) {
result.push(nums);
return;
}
for (let i = index; i < candidates.length; i++) {
dfs(value + candidates[i], i, [...nums, candidates[i]]);
}
};
dfs(0, 0, []);
return result;
};