欣迪

出處: 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
};

訂閱 IT-Monk

訂閱最新文章的發布消息! 😚😚😚
Loading

作者介紹 - 欣迪

欣迪

從設計到寫程式,發現自己有追求前端技巧的自虐傾向。不斷的踩坑,再從坑裡爬出來,慢慢對攀岩有點心得。 目前在多間公司擔任網站設計顧問。 同時也是網站架設公司負責人。