零、原題鏈接

77. 組合

一、題目描述

給定兩個整數 n 和 k，返回范圍 [1, n] 中所有可能的 k 個數的組合。

你可以按 任何順序 返回答案。

二、測試用例

示例 1：

輸入：n = 4, k = 2
輸出：
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]

示例 2：

輸入：n = 1, k = 1
輸出：[[1]]

提示：

1 <= n <= 20
1 <= k <= n

三、解題思路

1. 基本思路：
   ??回溯+剪枝，對于每個元素，我們可以選或者不選，如果太多次不選，可能無法構成指定長度的組合，則可以提前剪枝。
2. 具體思路：
   • 編寫 dfs 函數
     • 如果確定了 k 個元素，則記錄答案
     • 如果剩下的元素不足以構成長度為 k 的組合，則提前結束【剪枝】
     • 選擇這個元素，遞歸調用確定下一個元素的選取
     • 不選這個元素，遞歸調用確定下一個元素的選取
   • 調用 dfs 函數，返回結果

四、參考代碼

時間復雜度：$\mathrm{O}(C_n^k)$
空間復雜度：$\mathrm{O}(n)$

class Solution {
public:int _k;vector<vector<int>> ans;vector<int> t;void dfs(const int& n) {if (t.size() == _k) {ans.emplace_back(t);return;}if (n < _k - t.size()) // 提前剪枝return;t.emplace_back(n);dfs(n - 1);t.pop_back();dfs(n - 1);}vector<vector<int>> combine(int n, int k) {_k = k;dfs(n);return ans;}
};