经典递归问题,面试常考题
#include <iostream>
using namespace std;
const int N = 20;
int n;
bool st[N]; //题目要求输出方案需升序排列,故用一个st数组表示状态
void dfs(int u)
{
if (u > n)
{
for (int i = 1; i <= n; i ++ ) //从1到n,0不用枚举,小于n或小于u都可以
if (st[i])
cout << i << ' ';
cout << endl;
return;
}
st[u] = true;
dfs(u + 1); //选择当前树的分支
st[u] = false;
dfs(u + 1); //不选当前树的分支
}
int main()
{
cin >> n;
dfs(1);
return 0;
}