欣迪

出處: 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 <= 30
  • 1 <= candidates[i] <= 200
  • All elements of candidates are 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
};

訂閱 IT-Monk

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

作者介紹 - 欣迪

欣迪

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

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。