[LeetCode] 77. Combinations

轉自LeetCode

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

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

<Solution>

這題是要求幾取幾的問題，例如題目的例子就是 4 取 2 會有哪些組合

這種組合性的問題，很直覺會想到 DFS 的方式

因為題目有指明每個組合的長度，所以可以先準備好長度 k 的 vector，省掉 push_back 和 pop_back 的時間

code 如下
c++

kotlin
這題還有 iterative 的解法(參考資料)

特別說明一下 while 迴圈裡面有個檢查是 out[0] <= (n - k + 1)

這是因為每次都是小的數往上找組合

而小的數是有上限的，不然數字會不夠用

例如 n = 5, k = 3，則 out[0] 的上限會是 5 - 3 + 1 = 3

如果 out[0] = 4，那麼只剩下 5 還可以用，永遠都不可能找到三個數的組合

code 如下
c++