77. 组合 - 力扣（LeetCode）

1. class Solution {
2. private:
3.     vector<vector<int>> result;
4.     vector<int> path;
5.     void backtracking(int n, int k, int startIndex) {
6.         if (path.size() == k) {
7.             result.push_back(path);
8.             return;
9.         }
10.         for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) { // 优化的地方
11.             path.push_back(i); // 处理节点
12.             backtracking(n, k, i + 1);
13.             path.pop_back(); // 回溯，撤销处理的节点
14.         }
15.     }
16. public:
18.     vector<vector<int>> combine(int n, int k) {
19.         backtracking(n, k, 1);
20.         return result;
21.     }
22. };

复制代码

1. #include<iostream>
2. #include<bits/stdc++.h>
3. using namespace std;
5. vector<int>path;
6. vector<vector<int>>result;
8. void backtracking(int n,int k,int startindex)
9. {
10.     if(path.size()==k)
11.     {
12.         result.push_back(path);
13.         return ;
14.     }
15.     for(int i=startindex;i<=n;i++)
16.     {
17.         path.push_back(i);
18.         backtracking(n,k,i+1);
19.         path.pop_back();
20.     }
21. }
23. int main()
24. {
25.     int n,k;
26.     cin>>n>>k;
27.     backtracking(n,k,1);
28.    
29.     for (const auto& comb : result)
30.     {
31.         for (int num : comb)
32.         {
33.             cout << num << " ";
34.         }
35.         cout << endl;
36.     }
37.    
38.     return 0;
39. }

复制代码

 
剪枝操作: 

1. #include<iostream>
2. #include<bits/stdc++.h>
3. using namespace std;
5. vector<int>path;
6. vector<vector<int>>result;
8. void backtracking(int n,int k,int startindex)
9. {
10.     if(path.size()==k)
11.     {
12.         result.push_back(path);
13.         return ;
14.     }
15.     for(int i=startindex;i<=n-(k-path.size())+1;i++)
16.     {
17.         path.push_back(i);
18.         backtracking(n,k,i+1);
19.         path.pop_back();
20.     }
21. }
23. int main()
24. {
25.     int n,k;
26.     cin>>n>>k;
27.     backtracking(n,k,1);
28.    
29.     for (const auto& comb : result)
30.     {
31.         for (int num : comb)
32.         {
33.             cout << num << " ";
34.         }
35.         cout << endl;
36.     }
37.    
38.     return 0;
39. }

复制代码

输出二维数组

1. for (auto& j : result)
2.     {
3.         for (int i : j)
4.         {
5.             cout << i << " ";
6.         }
7.         cout << endl;
8.     }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。