文章目錄

• • 1. 題目來源
  • 2. 題目解析

1. 題目來源

鏈接：77. 組合

推薦題解：

• 官方有剪枝優化存在，值得細看。！
• weiwei哥的題解也相當不錯！

---

這個標題應該最先被搜到吧，必看的相關題目：

• [Mdfs] lc39. 組合總和(dfs+經典)
• [Mdfs] lc40. 組合總和 II(dfs+經典)
• [Mdfs] lc46. 全排列(dfs+經典)
• [Mdfs] lc47. 全排列 II(dfs搜索順序+去重處理+知識理解+經典)
• [Mdfs] lc77. 組合(組合類型枚舉+題目總結+經典)
• [Mdfs] lc78. 子集(二進制枚舉+排列類型枚舉+經典)
• [Mdfs] lc90. 子集 II(組合類型枚舉+多重背包+去重經典)

2. 題目解析

典型的組合類型枚舉問題。保證枚舉順序即可，即 path[] 數組中的元素是遞增的，以此來保證枚舉方案的唯一性。

代碼：

class Solution { public:vector<vector<int>> res;vector<int> path;void dfs(int start, int cnt, int n, int k) {if (cnt == k) {res.push_back(path);return ;}for (int i = start; i <= n; i ++ ) {path.push_back(i);dfs(i + 1, cnt + 1, n, k);path.pop_back();}}vector<vector<int>> combine(int n, int k) {dfs(1, 0, n, k);return res;} };

---

其實，這也就是經典的組合問題，就是從 n 個數中選 k 個，每個數有兩種狀態，選 / 不選，沒有重復元素的出現。

那么可以順序來做，考慮每個數的狀態，選 / 不選。有點像遞歸實現排列類型枚舉，但是在此我們只挑選選了 k 個的方案。

這個雖說是 $O(2^n)$ 種方案，和二進制枚舉差不多，但是有剪枝的存在，也還是很快。

class Solution { public:vector<vector<int>> res;vector<int> path;void dfs(int u, int cnt, int n, int k) {if (cnt == k) {res.push_back(path);return ;}// 要加這個剪枝，否則將無限搜下去，所有數都不選...// 且應該在后面加這個剪枝，因為第 n 個數可能選完后即構成答案，// 次數遞歸進入下一層，cnt=n+1, 剛好需要將答案加進去，不能直接 return;// 所以要在上面的 if 后面這判斷if (u == n + 1) return ; // 不選dfs(u + 1, cnt, n, k);// 選path.push_back(u);dfs(u + 1, cnt + 1, n, k);path.pop_back();}vector<vector<int>> combine(int n, int k) {dfs(1, 0, n, k);return res;} };

---

當然，這種每個數兩種情況的枚舉，也可以使用二進制枚舉的方式！

沒有任何剪枝，非常非常慢… 比上面同想法的遞歸實現，慢了 50 倍…

官方有剪枝優化存在，值得細看。！

class Solution { public:vector<vector<int>> combine(int n, int k) {vector<vector<int>> res;for (int i = 0; i < 1 << n; i ++ ) {int cnt = 0;vector<int> path;for (int j = 30; ~j; j -- ) if (i >> j & 1) path.push_back(j + 1);if (path.size() == k) res.push_back(path);}return res;} };

總結

以上是生活随笔為你收集整理的[Mdfs] lc77. 组合(组合类型枚举+题目总结+经典)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。