[递归] 指数型枚举

题目描述

? 从?1?n?这?n?个整数中随机选取任意多个，每种方案里的数从小到大排列，按字典序输出所有可能的选择方案。

---

输入

? 输入一个整数?n。（1≤n≤10）

输出

? 每行一组方案，每组方案中两个数之间用空格分隔。

? 注意每行最后一个数后没有空格。

---

样例输入

3

样例输出

1
1 2
1 2 3
1 3
2
2 3
3

样例输入2

4

样例输出2

1
1 2
1 2 3
1 2 3 4
1 2 4
1 3
1 3 4
1 4
2
2 3
2 3 4
2 4
3
3 4
4

---

数据规模与约定

? 时间限制：1 s

? 内存限制：256 M

? 100% 的数据保证?1≤n≤10

解题分析

本题要求我们去按照字典序去枚举排列，我们考虑使用递归函数去枚举，并且用一个数组去记录我们枚举的结果，并在一个合适的位置去输出。

我们设定一个函数f(i,j)，i表示我们当前枚举的位置，而j表示当前我们枚举的位置最小可以放置的数字。这样可以保证我们在不断向后递归的过程中可以确保数字是递增的。

使用递归的方式来解决问题，通过不断调用自身来生成所有可能的选择方案。下面是对代码解决问题的思路和想法的详细阐述：

1. 首先，代码定义了一个全局变量n和一个数组array，用于存储选择方案中的数字。

2. printfresult?函数用于打印当前选择方案中的数字，它接受一个参数l，表示当前选择方案的长度。该函数会遍历数组array，打印数组中的元素，并在最后一个元素后面不加空格。

3. f?函数是核心函数，它用于生成所有可能的选择方案。它接受两个参数，i和j，表示当前选择方案的长度和下一个要选择的数字。该函数的逻辑如下：

   • 首先，判断递归结束的条件。如果i大于等于n或者j大于n，说明已经选择完毕，直接返回。
   • 然后，使用一个循环从j遍历到n，将当前数字k存入数组array的第i个位置。
   • 调用printfresult函数打印当前选择方案。
   • 递归调用f函数，将i加1，j加1，继续生成下一个选择方案。

4. main?函数用于读取输入和调用f函数。首先，读取输入的整数n。然后，调用f函数，初始时i为0，j为1，开始生成选择方案。

这段代码的思路比较简单，通过递归和循环的组合，实现了生成所有可能的选择方案并按照要求输出的功能。代码的时间复杂度为O(2n)，因为对于每个数字，都有选择和不选择两种情况，总共有2^n种情况。代码的空间复杂度为种情况。代码的空间复杂度为O(n)，因为使用了一个长度为n的数组来存储选择方案。

#include <iostream>
using namespace std;

int n,array[10];

void printfresult(int l){
	for(int i=0;i<=l;i++){
		printf("%d",array[i]);
		if(i!=l) printf(" ");
		else printf("\n");
	}
}


void f(int i,int j){
	if(i>=n || j>n){
		return;
	}
	for(int k=j;k<=n;k++){
		array[i]=k;
		printfresult(i);
		f(i+1,k+1);
	}
}


int main(){
	scanf("%d",&n);
	f(0,1);
	return 0;
}