0077. Combinations (Medium)

Question

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

Example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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學演算法，我們下次見囉，掰~