算法--递归实现【DFS】

题目：指数型枚举

从 1∼n这 n 个整数中随机选取任意多个，输出所有可能的选择方案。

输入格式

输入一个整数 n。

输出格式

每行输出一种方案。

同一行内的数必须升序排列，相邻两个数用恰好 11 个空格隔开。

对于没有选任何数的方案，输出空行。

本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

数据范围

1≤n≤15

输入样例：

3

输出样例：

  

1

2

3

1 2

1 3

2 3

1 2 3

注意：输出时有空集

AC代码：

#include<iostream>
#include<cstdio>using namespace std;const int N = 20;
int n;
int st[N];void dfs(int u)
{if(u>n){for(int i=1;i<=n;i++){if(st[i]==1){//输出时只输出选中的树枝cout<<i<<' ';}}cout<<endl;return;}st[u]=2;//不选中dfs(u+1);st[u]=0;st[u]=1;//选中dfs(u+1);st[u]=0;return;
}int main()
{cin>>n;dfs(1);return 0;
}

题目：排列型枚举

把 1∼n 这 n个整数排成一行后随机打乱顺序，输出所有可能的次序。

输入格式

一个整数 n。

输出格式

按照从小到大的顺序输出所有方案，每行 11 个。

首先，同一行相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。

数据范围

1≤n≤91≤n≤9

输入样例：

3

输出样例：

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

AC代码：

#include<iostream>
#include<cstdio>using namespace std;int n;
int path[10];
bool sta[10];void dfs(int u)
{if(u>n){for(int i=1;i<=n;i++){cout<<path[i]<<' ';}cout<<endl;return;}for(int i=1;i<=n;i++){if(sta[i]==false){sta[i]=true;path[u]=i;u++;dfs(u);u--;sta[i]=false;}}return;
}int main()
{scanf("%d",&n);dfs(1);return 0;
}