算法竞赛进阶指南0x00基本算法 0x02递推与递归 例题递归实现指数型枚举

题目

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

输入格式

输入一个整数 n。

输出格式

每行输出一种方案。

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

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

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

数据范围

1≤n≤15

输入样例：

3

输出样例：

3

2

2 3

1

1 3

1 2

1 2 3

// A code block
var foo = 'bar';
           

import java.util.Scanner;

public class Main {
	static int n;
public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();//1~n
		dfs(0,0);//(第i位，最终state状态)
		
}
	private static void dfs(int cur, int state) {
		if(cur==n) {
			for (int i = 0; i < n; i++) {
				if(((state>>i)&1)==1) {
					System.out.print(i+1+" ");
				}
			}
			System.out.println();
			return;
		}
		dfs(cur+1, state|1<<cur);
		dfs(cur+1, state);
	}
}