出處： https://leetcode.com/problems/combination-sum-ii/
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.
Each number in candidates may only be used once in the combination.
Note: The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5 Output: [ [1,2,2], [5] ]
Constraints:
1 <= candidates.length <= 1001 <= candidates[i] <= 501 <= target <= 30
這是上一題的進階版：解題 50. Combination Sum
解法也差不多，這題的數字使用次數是有上限的。而且數字的排列是隨機的。
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum2 = function(candidates, target) {
// 搜集結果用的陣列
const output = []
// 用來記錄使用過的數字
const numsUsed = []
// 先對數字進行由小到大的排列，以便進行處理
candidates.sort((a, b) => a - b)
// 開始迴圈
for (let i = 0; i < candidates.length; i++) {
// 如果數字已經被使用過，就進入下一個迴圈
if (numsUsed.includes(candidates[i])) {
continue
} else {
numsUsed.push(candidates[i])
}
// 這邊要做好進入圈後遞迴的準備
// candidates[i] 是一定要放進去的數字，所以先把自己扣掉，計算剩下數字所需的和 newTarget
const newTarget = target - candidates[i]
// 如果 newTarget 是零，則表示不用再補任何數字，
// 可以在 output 加入 [candidates[i]] 的組合
if (newTarget === 0) {
output.push([candidates[i]])
}
// 因為我們之前有把數字由小到大排列，所以下一個數字 candidates[i + 1]，一定大於等於 candidates[i]
// 所以 newTarget 是負數或零，立刻中斷迴圈，避免資源的浪費，因為下一個數字不會比 candidates[i] 小。
if (newTarget <= 0) break
// 接下來利用遞迴的方式取得剩下數字的組合
const _candidates = candidates.slice(i + 1)
const res = combinationSum2(_candidates, newTarget)
// 把 candidates[i] 加回每個結果的開頭
for (let j = 0; j < res.length; j++) {
output.push([candidates[i], ...res[j]])
}
}
return output
};
