從LeetCode學演算法 - 63 Backtracking (4) / DFS (6)

0077. Combinations (Medium)

寫在前面： 請幫我隨手點開下面的SHOW EMBED並按5個like~ (按讚不用錢，感謝支持寫作~)

Question: Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

Example:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

分析/解題： 給定兩個整數n跟k，回傳所有1~n之間取k個數字的組合。

這題其實跟先前的0078. Subsets非常的接近， 差別在於我們必須改成取得固定k個， 所以現在考慮上必須要將「目前將取到第幾個數字」這件事情納入考量。

那麼，我們可以同樣用backtracking(回溯法)的方式來考慮。 我們考慮初始化一個組合combo，從1開始決定要不要加入組合中， 並記錄現在走到的index(以i表示)。

那麼，我們需要傳入的參數值有： combo(當前未完成的組合), res(記錄結果的所有已完成的組合), n(1~n的數字), k(連同當前這輪，還有幾個數字要被納入組合), i(當前走到的數字)

那麼，我們可以使用遞迴(命名為findCombos)來處理這題， 當k等於0時，表示已經完成這個組合，將其加入res中； 否則當i ≤ n 時，表示還有可以選擇的數字(且組合還沒完成)， 此時可以分成 a. 將i加入combo 或 b. 不加入combo 中。 a. 將i加入combo中的話 -> 代入findCombos的遞迴中k要減1，i要加1。 且這輪下去遞迴完以後，記得將狀態復原(把combo的最後一個數字拿掉) b. 不將i加入combo的話 -> 代入findCombos的遞迴僅需i要加1即可。 (因為只有當前選擇的數字增加)

除此以外，我們可以額外考慮一件事情： 由於剩下的可選數字應該大於我們還需要選擇的數字， 所以 i≤n 的條件應該可以進一步縮限成 i+k-1 ≤ n。

依此，寫成如下的程式碼。

Java的部分，可以使用ArrayList/LinkedList皆可， 並且保險起見，可以先行檢查n和k。 (畢竟測資也有可能弄個不合法的負數或零)

Java:

如之前的文章，Python請不要忘記append到combo上的必須是複製的list。 此外也可以使用itertools的combination來直接得到答案， 但請不要在面試的時候這樣用XD (因為這只證明了你知道工具，而不是你懂回溯法)

Python:

面試實際可能會遇到的問題： 「時間/空間複雜度？」 (O(C(n, k))/O(k*C(n,k))。 由於k的値會影響階乘連接的個數，所以不好化簡。)

相似及延伸： Special Thanks suggestions/corrections from viewers: (歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

如果你／妳覺得這篇文章不錯，請給我5個Like。(點開SHOW EMBED!)
也請記得「Follow」我，隨時收看最新的文章。