递归
例题
递归实现指数型枚举
从 1∼n这 n个整数中随机选取任意多个，输出所有可能的选择方案。
输入格式
输入一个整数 n。
输出格式
每行输出一种方案。
同一行内的数必须升序排列，相邻两个数用恰好 1 个空格隔开。
对于没有选任何数的方案，输出空行。
各行（不同方案）之间的顺序任意。
数据范围
1≤n≤15
输入样例：
3输出样例：
3 2 2 3 1 1 3 1 2 1 2 3
import java.util.*;
public class Main{
static int N=16;
static int n;
static int []st=new int[N]; //表状态，0表示未考虑，1表示选，2表示不选
static void df(int u){
if(u>n){ //递归出口，输出选择的数
for(int i=1;i<=n;i++){
if(st[i]==1)
System.out.print(i+" ");
}
System.out.println();
return ;
}
//也可不恢复现场
st[u] =2; //未选择，递归第一个选的分支
df(u+1);
st[u] =0; //恢复现场
st[u]=1;//第二个分支，选了
df(u+1);
st[u]=0;//恢复现场
}
public static void main(String[] args){
Scanner scan =new Scanner(System.in);
n=scan.nextInt();
df(1);
scan.close();
}
}递归实现排列型枚举
把 1∼n 这 n个整数排成一行后随机打乱顺序，输出所有可能的次序。
输入格式
一个整数 n。
输出格式
按照从小到大的顺序输出所有方案，每行 1 个。
首先，同一行相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。
数据范围
1≤n≤9
输入样例：
3输出样例：
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
import java.util.*;
public class Main{
static int N=10;
static int[] st=new int[N]; //存放第u个位置放什么数
static boolean[] use=new boolean[N];//表示是否选用了i
static int n;
public static void dfs(int u){
if(u>n){ //递归出口,表示u个位置都已存放数
for(int i=1;i<=n;i++){
System.out.print(st[i]+" ");
}
System.out.println();
return ;
}
//枚举每个分支
for(int i=1;i<=n;i++){
if(!use[i]){ //如果数i没有用过
st[u]=i; //第u个位置放i
use[i]=true;
dfs(u+1);
//恢复现场
st[u]=0; //第u个位置未选用i
use[i]= false;
}
}
}
public static void main(String[] args){
Scanner scan=new Scanner(System.in);
n=scan.nextInt();
dfs(1);
scan.close();
}
}时间复杂度：n*(1+n+n(n-1)+......+n!)<n*3n!
