出處： https://leetcode.com/problems/combination-sum/
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.
It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
Example 1:
Input: candidates = [2,3,6,7], target = 7 Output: [[2,2,3],[7]] Explanation: 2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times. 7 is a candidate, and 7 = 7. These are the only two combinations.
Example 2:
Input: candidates = [2,3,5], target = 8 Output: [[2,2,2,2],[2,3,3],[3,5]]
Example 3:
Input: candidates = [2], target = 1 Output: []
Constraints:
1 <= candidates.length <= 301 <= candidates[i] <= 200- All elements of
candidatesare distinct. 1 <= target <= 500
最近真的很常用到遞迴方法呢！
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function(candidates, target) {
// 做一個用來搜集結果的陣列
const output = []
// 開始每一個數字的迴圈
for (let i = 0; i < candidates.length; i++) {
// 把目前的數字拿掉，用目標減去，看看還需要湊多少數字
const numberWeNeed = target - candidates[i]
if (numberWeNeed === 0) {
// 如果等 target === candidates[i]，那就把數字本身加入結果
output.push([target])
} else if (numberWeNeed < 0) {
// 如果需要的數字是負數，則跳過，進入下一個數字
continue
}
// 用剩下的數字進行遞迴
const _candidates = candidates.slice(i)
// 取得剩下的數字遞迴的結果
const res = combinationSum(_candidates, numberWeNeed)
// 把所有的結果開頭加上 candidates[i] ， 並加入 output
for (let j = 0; j < res.length; j++) {
output.push([candidates[i], ...res[j]])
}
}
return output
};
