AcWing 93. 递归实现组合型枚举
原题链接
简单
作者:
尘下吹霜
,
2023-11-22 10:09:05
,
所有人可见
,
阅读 54
算法1 DFS
(暴力枚举)
Java 代码
import java.util.Scanner;
public class Main {
static int r;
static int n;
static int []arr; // 记录位置 数组
/** 递归搜索
*
* @param x 当前位置
* @param size 下一个位置从几开始枚举
*/
static void dfs(int x, int start) {
// 剪枝, 减少递归
// 上一位置 + 剩余可选数 数量 < 需要位置数, 退出
if((x - 1) + (n - start + 1) < r)
return;
// 边界判定
if(x > r) {
for(int i = 1; i < arr.length; i++) {
// 注意: 题目要求三个场宽, 以下格式, 前面打两个空格可能出错
System.out.print(arr[i] + " ");
}
System.out.println();
return;
}
// 循环选择递归
for(int i = start; i <= n; i++) {
// 选择
arr[x] = i;
dfs(x+1, i+1); // 下个位置从i的下一个数开始枚举
// 恢复现场
arr[x] = 0; // 先自减再赋值
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
r = sc.nextInt();
sc.close();
arr = new int[r+1];
dfs(1, 1);
}
}