AcWing 93. DFS递归实现组合型枚举(Java)
原题链接
简单
作者:
差一点睡死了
,
2021-02-10 14:54:48
,
所有人可见
,
阅读 275
DFS递归实现组合型枚举
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int n,m;
static boolean[] st=new boolean[100]; //使用记忆数组
static void dfs(int u,int count) {
if(count+n-u<m) {//如果剩下的数凑不到m个
return;
}
if(count==m) {
for (int i = 0; i <n; i++) {
//遍历记忆化数组 从小到大输出结果
if(st[i]) {
System.out.print(i+1+" ");
}
}
System.out.println();
//每一次输出完一定要return 不然栈溢出
return;
}
st[u]=true;//true表示选了这个u这个数
dfs(u+1,count+1);
//开始回溯
st[u]=false;
dfs(u+1,count);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] read = br.readLine().split(" ");
n = Integer.parseInt(read[0]);
m = Integer.parseInt(read[1]);
dfs(0, 0);// 枚举到哪了,选了多少个
}
}