出處: 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 <= 100
1 <= candidates[i] <= 50
1 <= 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 };