搜索
简帛阁>技术文章>[AcWing] 递归实现指数型枚举

[AcWing] 递归实现指数型枚举

递归实现指数型枚举

题目

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

输入格式

输入一个整数n。

输出格式

每行输出一种方案。

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

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

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

数据范围

1 ≤ n ≤ 15 1≤n≤15 1≤n≤15

输入样例

3

输出样例

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

题解

思路

  • 每个数字有两种情况:选或者不选,这里我们用 p[] 数组来记录其是否被选择

注意

  • DFS 当 u == n 时,需要 return,否则会导致 Segmentation Fault
#include <iostream>

using namespace std;

const int N = 20;
int n, p[N], dx[] = {<!-- -->0, 1};

void dfs(int u) {<!-- -->
    if (u == n) {<!-- -->
        for (int i = 0; i < n; i ++)
            if (p[i]) cout << i + 1 << " ";
        cout << endl;
        return;
    }
    
    for (auto x : dx) {<!-- -->
        p[u] = x;
        dfs(u + 1);
    }
}

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