AcWing-1-递归实现指数型枚举
题目
从 1∼n1∼n 这 nn 个整数中随机选取任意多个，输出所有可能的选择方案。
输入格式
输入一个整数 nn。
输出格式
每行输出一种方案。
同一行内的数必须升序排列，相邻两个数用恰好 11 个空格隔开。
对于没有选任何数的方案，输出空行。
本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。
思路
从第一个位置开始选择，每个数字都有选择和不选择两种情况，选择完后，再跳到下一个位置继续选择，如果当前位置超过了数字所在位置的最大值，那么就终止递归，并且按照已经选择的数字进行打印输出
Q：如何表示目前所在位置？
A：通过变量u来表示当前所处的位置
Q：如何跳到下一个位置？
A：通过使u+1，并递归调用方法来表示跳到下一个位置进行判断
Q：如何记录当前位置是否选择？
A：通过数组来记录
Q：什么叫恢复现场？
A：根据递归二叉树可知，递归的调用顺序是中序遍历，左根右，根代表当前位置，左和右代表的是下一个位置，从左回到根时，需要撤销在左节点进行的操作，防止干扰下一个位置
代码
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] arr = new int[n+1]; //记录状态，0表示没考虑，1表示选，2表示不选 f(1,n,arr); } static void f(int u,int n,int[] arr){ //u为当前所处的位置，n为数字的个数 //当前位置大于总数字个数 if(u > n){ for(int i = 1; i <= n; i++){ if(arr[i] == 1) System.out.print(i + " "); } System.out.println(); return; } //当前位置的数选 arr[u] = 1; f(u+1,n,arr); //恢复现场 arr[u] = 0; //当前位置的数不选 arr[u] = 2; f(u+1,n,arr); //恢复现场 arr[u] = 0; } }
总结
可以用画递归二叉树的方法来判断递归的调用过程