创建一个state,其第u位是1 state | 1<
代码1
注意:
第一个是空集
- #include<bits/stdc++.h>
- using namespace std;
-
- typedef long long ll;
- #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
- const int N = 20;
-
- int n;
- bool state[N];
-
- void dfs(int u)
- {
- if(u > n) //叶子节点
- {
- //遍历输出结果
- for(int i = 1;i <= n;i ++ )
- if(state[i]) //看第i位是否为1
- cout << i <<' ';
- cout<<endl;
- return;
- }
-
- state[u] = true; // 选择当前u
- dfs(u + 1);
-
- state[u] = false; //不选
- dfs(u + 1);
- }
-
- int main()
- {
- IOS;
- cin>>n;
- dfs(1);
- return 0;
- }
- #include<bits/stdc++.h>
- using namespace std;
-
- typedef long long ll;
- #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
- const int N = 20;
-
- int n;
- int state[N];
- bool used[N];
-
- void dfs(int u)
- {
- if(u > n) //边界
- {
- //遍历输出结果
- for(int i = 1;i <= n;i ++ )
- cout << state[i] <<' ';
- cout<<endl;
- return;
- }
-
- //枚举每个位置存放数
- for(int i = 1; i <= n; i ++)
- {
- if(!used[i]){
- state[u] = i;
- used[i] = true;
- dfs(u+1);
- //恢复
- used[i] = false;
- state[u] = 0;
- }
- }
- }
-
- int main()
- {
- IOS;
- cin>>n;
- dfs(1);
- return 0;
- }
- #include<bits/stdc++.h>
- using namespace std;
-
- typedef long long ll;
- #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
- const int N = 20;
-
- int n;
- vector<int> used;
-
- void dfs(int u, int state)
- {
- if(u == n) //边界
- {
- //遍历输出结果
- for (auto x : used) cout << x <<' ';
- cout<<endl;
- return;
- }
-
- //枚举每个位置存放数
- for(int i = 0; i < n; i ++)
- {
- if(!(state >> i & 1))
- {
- used.push_back(i + 1);
- dfs(u + 1, state | 1 << i);
- used.pop_back();
- }
- }
- }
-
- int main()
- {
- IOS;
- cin>>n;
- dfs(0,0);
- return 0;
- }
- #include<bits/stdc++.h>
- using namespace std;
-
- typedef long long ll;
- #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
-
- int main()
- {
- IOS;
- int n;
- cin>>n;
- //优化,dp滚动数组的雏形
- int a = 0, b = 1;
- for(int i = 0; i < n; i++)
- {
- cout<<a<<" ";
- int fn = a + b;
- a = b, b = fn;
- }
- }