搜索
简帛阁>技术文章>递归实现指数型枚举--ACwing 92.题解

递归实现指数型枚举--ACwing 92.题解

题目:

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

输入格式

输入一个整数 nn。

输出格式

每行输出一种方案。

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

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

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

数据范围

1≤n≤15

输入样例:

3

输出样例:

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

 很明显这是递归三大类型之一:指数型枚举

所以我们可以有递归搜索树来实现,对于 1~n 中的每一个数,它都有两种情况:选了或没选。所以以此我们可以建立一个递归搜索树。

思路:

对于递归不熟练可以画对应的递归搜索树
按照**每个位置**考虑,每个位置有**三种状态**:未考虑、不填、填
对此可以用数组才存取每个位置的状态:未考虑为0,不填为2,填为1
对于状态改变注意恢复现场,这题因为状态会被覆盖所以可以不用恢复现场

代码实现:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int st[16]; //记录状态,0-没考虑,1-选了,2-没选。
int N;

void dfs(int n)
{
    if(n > N) //设置边界,输出。
    {
        for(int i = 1; i <= n; ++i)
            if(st[i] == 1) 
            printf("%d ",i);
        printf("\n");
        return;
    }
    //
    st[n] = 2; //第一个分支--没选
    dfs(n + 1); //调用自己--进入下一个分支
    st[n] = 0; //回溯时要还原
    
    st[n] = 1;  //第二个分支--选了
    dfs(n + 1);
    st[n] = 0;
}

int main()
{
    cin >> N;
    
    dfs(1);
    
    return 0;
}

题目:从1∼n这nn个整数中随机选取任意多个,输出所有可能的选择方案。输入格式输入一个整数nn。输出格式每行输出一种方案。同一行内的数必须升序排列,相邻两个数用恰好1个空格隔开。对于没有选任何数的方案
AcWing92递归实现指数枚举题目描述从1∼n1∼n1∼n这nnn个整数中随机选取任意多个,输出所有可能的选择方案。输入格式输入一个整数nnn。输出格式每行输出一种方案。同一行内的数必须升序排列
这个系列是蓝桥杯的训练,为了蓝桥杯,同时也是日常的算法训练。第一题是递归,有点类似递归的全排列的做法,复习基本的递归模板。ProblemimportjavaioBufferedReader;impor
题目描述从1~n这n个整数中随机选取任意多个,输出所有可能的选择方案。输入格式输入一个整数n。输出格式每行输出一种方案。同一行内的数必须升序排列,相邻两个数用恰好1个空格隔开。对于没有选任何数的方案,
AcWing92递归实现指数枚举(深搜)写在前面:AcWing是由北大一神级人物——“大雪菜”创办的算法交流社区,里面除了正常oj网站的功能之外,还提供单人训练、双人匹配、云端操作系统等模式,除此之
AcWing92递归实现指数枚举(遍历)写在前面:AcWing是由北大一神级人物——“大雪菜”创办的算法交流社区,里面除了正常oj网站的功能之外,还提供单人训练、双人匹配、云端操作系统等模式,除此之
递归实现指数枚举题目从1~n这n个整数中随机选取任意多个,输出所有可能的选择方案。输入格式输入一个整数n。输出格式每行输出一种方案。同一行内的数必须升序排列,相邻两个数用恰好1个空格隔开。对于没有
题目:把1∼n这n个整数排成一行后随机打乱顺序,输出所有可能的次序。输入格式一个整数n。输出格式按照从小到大的顺序输出所有方案,每行1个。首先,同一行相邻两个数用一个空格隔开。其次,对于两个不同的行,
题目:从1∼n这n个整数中随机选出m个,输出所有可能的选择方案。输入格式:两个整数n,m,在同一行用空格隔开。输出格式:按照从小到大的顺序输出所有方案,每行1个。首先,同一行内的数升序排列,相邻两个数
AcWing94递归实现排列枚举题目描述把1∼n1∼n1∼n这nnn个整数排成一行后随机打乱顺序,输出所有可能的次序。输入格式一个整数nnn。输出格式按照从小到大的顺序输出所有方案,每行111个。