题解描述
构建递归树(深度为 n 的完全二叉树),dfs 搜索
时间复杂度O(2^n),也可以从N的范围(<16)看出来
(输出时还有一个线性的 O)
C++代码
#include <iostream>
#include <algorithm>
using namespace std;
int state[16];
int n;
//dfs的常见写法!
void dfs(int u){
if(u>n) {//当到达某个叶节点,输出当前路线的方案
for(int i=1;i<=n;i++){
if (state[i]==1) cout << i << " ";
}
cout << endl;
return;
}
state[u]=1;//选
dfs(u+1);
state[u]=0;//还原现场
state[u]=2;//不选,其实可以是0,但2更有利于理解还原现场
dfs(u+1);
state[u]=0;
}
int main(){
cin >> n;
dfs(1);//按照题意是从1开始搜
return 0;
}
一个dfs 里不用 for,因为每层只经历一次,代表选不选当前的数