iT邦幫忙

2017 iT 邦幫忙鐵人賽
DAY 30
0
自我挑戰組

LeetCode - 30 Days系列 第 30

[Leetcode-30/30][Combinations] #39 Combination Sum、結語

#39 Combination Sum

同步發佈於 Github repo

題目難度:Medium

題目敘述:

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7, 
A solution set is: 

[
  [7],
  [2, 2, 3]
]

題目解答:

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
const dfs = (start, target, candidates, sum, curArr, result) => {
  if(sum === target) {
    result.push(curArr.concat());
  }
  
  for(let i = start; i < candidates.length; i++) {
    if(sum + candidates[i] <= target) {
      curArr.push(candidates[i]);
      dfs(i, target, candidates, sum + candidates[i], curArr, result);
      curArr.pop();
    }
  }
}; 
 
const combinationSum = (candidates, target) => {
  let result = [];
  candidates.sort((a, b) => {
    return a > b ? 1 : -1;
  })
  
  dfs(0, target, candidates, 0, [], result);
  
  return result;
};

題目連結:39. Combination Sum

解題說明:

終於來到最後一天啦啦啦啦啦!!!!!
三十天的 leetcode 要結束了!!!!!

我們先來解最後一題吧~題目給我們一個陣列裡面裝可以用的數字,和一個數字,我們要用陣列裡的數字去組合出這個數字,
昨天的題目很像,但這次除了組合,還多了總和的概念,不過大致上想法一模一樣~
一樣是用 DFS 去解,下面會詳細說明!

解題步驟:

  • 步驟 1.
    我們先幫 candidates 進行排序,是方便後面用加的方式可以少遞迴一些,
    然後我們把參數傳進去 dfs()
const combinationSum = (candidates, target) => {
  let result = [];
  candidates.sort((a, b) => {
    return a > b ? 1 : -1;
  })
  
  dfs(0, target, candidates, 0, [], result);
  
  return result;
};
  • 步驟 2.
    這裡是主要遞迴的部分,
    首先,只有 sum === target 時我們才要把這個組合放進答案 result 裡,

    接著,一樣一次放一個數字進去加看看,要注意的是,傳給 dfs 的第一個參數 i 不需要 +1,因為 i 是可以重複使用的,如果說不能重使用的話,那就不能讓 i 在下一次遞迴時還跟這次一樣了!
    然後跑完一次遞迴要 pop 掉一個空位給下一個數字進來家看看,完成!

const dfs = (start, target, candidates, sum, curArr, result) => {
  if(sum === target) {
    result.push(curArr.concat());
  }
  
  for(let i = start; i < candidates.length; i++) {
    if(sum + candidates[i] <= target) {
      curArr.push(candidates[i]);
      dfs(i, target, candidates, sum + candidates[i], curArr, result);
      curArr.pop();
    }
  }
}; 

結語

很開心自己終於撐過去 30 天了!從本來對演算法、資料結構沒什麼把握,到現在總算都先 run 過一點,對題目也有點感覺了,
但這樣明顯還是不夠的,如果要去應徵大公司的話至少要刷個一兩百題才夠吧,
而且還要訓練到一看到題目至少就能在腦子裡順好怎麼寫了,不然面試當場會緊張,時間也沒有那麼多,一慌就很難想到解法了!
希望能以此 30 篇基礎的 leetcode 題當作開頭,未來在面對新題目時可以不至於沒有想法,也祝大家 2017 年快樂了!
謝謝大家的支持!


上一篇
[Leetcode-29/30][Combinations] #77 Combinations
系列文
LeetCode - 30 Days30

尚未有邦友留言

立即登入留言