題目網址：https://leetcode.cn/problems/combinations/

題意：給兩個整數 n 和 k, 以任意順序返回 [1, n] 中所有可能的 k 個數組合。

Solution：

想法：取每個 i 輪流當開頭, 其中 i 的範圍是 [1, n], 並從 [i + 1, n] 取 k - 1 個（從 i + 1 取必不會重複到前面）。dfs() 中的 for loop 是取 j + 1, 因為若取 i + 1, 則當 j > i + 1 後, 便會取到重複的組合。
e.g. n = 3, k = 2, 其中 [1, 2], [2, 1] 不能同時出現

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        dfs(1, n, k);
        return res;
    }

private:
    vector<int> cur;
    vector<vector<int>> res;

    void dfs(const int i, const int n, const int k){
        if (k == 0) {
            res.emplace_back(cur);
            return;
        }

        for (int j = i; j <= n; ++j) {
            cur.emplace_back(j);
            dfs(j + 1, n, k - 1);
            cur.pop_back();
        }
    }
};
  • time：$O(k \cdot \binom{n}{k})$ ➔ $\binom{n}{k}$ 種組合, 每種組合需 $O(k)$ time
  • space：$O(k \cdot \binom{n}{k})$ ➔ $O(k) + O(k \cdot \binom{n}{k}) + O(k)$
    • $O(k)$：dfs() 最大遞迴深度
    • $O(k \cdot \binom{n}{k})$：$\binom{n}{k}$ 種組合, 每種組合長度為 k
    • $O(k)$：cur 最大長度