leetcode:暴力枚举法之Combinations
题目;
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], ]
即:求 C(n, k) 的所有组合,且没有顺序之分
c++实现:
#include <iostream> #include <vector> #include <algorithm> #include <numeric> using namespace std; void dfs(int n, int k, int start, int cur,vector<int> &path, vector<vector<int> > &result) ; //递归 vector<vector<int> > combine(int n, int k) { vector<vector<int> > result; vector<int> path; dfs(n, k, 1, 0, path, result); return result; } void dfs(int n, int k, int start, int cur,vector<int> &path, vector<vector<int> > &result) { if (cur == k) result.push_back(path); for (int i = start; i <= n; ++i) { path.push_back(i); dfs(n, k, i + 1, cur + 1, path, result); path.pop_back(); } } //迭代,使用prev_permutation()函数 //vector<vector<int> > combine(int n, int k) //{ // vector<int> values(n); // iota(values.begin(), values.end(), 1);//需要注意的是iota初始化的序列需要指定大小values(n). // vector<bool> select(n, false); // fill_n(select.begin(), k, true); // vector<vector<int> > result; // do{ // vector<int> one(k); // for (int i = 0, index = 0; i < n; ++i) // if (select[i]) // one[index++] = values[i]; // result.push_back(one); // } while(prev_permutation(select.begin(), select.end())); // return result; //} int main() { int n=4,k=2; vector<vector<int>> out; out= combine(n, k); vector<vector<int>>::iterator pp; vector<int>::iterator it; for(pp=out.begin();pp<out.end();pp++) { for (it=(*pp).begin();it<(*pp).end();it++) { cout<<*it<<" "; } cout<<endl; } return 0; } 测试结果;