输出一个集合a[1~n]的全部子集。
思路:
这是全组合问题。首先解决n个元素里取k个元素,然后循环调用即可。
用递归解决。从后往前扫描,a[n]有两种情况:被选中;没被选中。如果被选中,子问题是从a[1~n-1]中选k-1个元素;如果没被选中,子问题是从a[1~n-1]中选k个元素。递归的终止条件是k==1。
#include <iostream> #include <vector> using namespace std; void CombRecur(vector<int>& ivec, vector<int>& res, int n, int k); void Comb(vector<int>& ivec) { int size = ivec.size(); for (int i = 0; i < size; ++i) { vector<int> res(i+1); CombRecur(ivec, res, size, i + 1); } } void CombRecur(vector<int>& ivec, vector<int>& res, int n, int k) { for (int i = n; i >=k; --i) { //res保存下标 res[k - 1] = i - 1; if (k > 1) CombRecur(ivec, res, i - 1, k - 1); else { for (int j = 0; j < res.size(); ++j) cout << ivec[res[j]] << ' '; cout << endl; } } } void main() { int a[] = {1, 2, 3}; vector<int> ivec(a, a + 3); Comb(ivec); }