AcWing-92-递归实现指数型枚举

2021-01-26 · 121次阅读 · 原创 · 数据结构与算法

#题解 #递归与递推

问题

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

输入格式

输入一个整数n。

输出格式

每行输出一种方案。

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

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

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

数据范围

1 ≤ n ≤ 15

输入样例：

输出样例：

思路

思路一

递归，先设置n个空位，从0开始到n-1的每个位置进行选择，当前位置是填还是不填，当位置枚举完一次（及k==n）的时候，进行输出，按照arr数组的每个位置的选择还是不选择进行输出。

思路二

从每个数字开始往后升序递归，若其后面有大于本身数字，则一直递归下去，形成森林（如下图），森林的每一层都需要打印，但子节点打印时需将前面的所有祖先节点都打印。dfs(i,k)表示当前为第i个数字，前面有k个数字。

题解

题解一

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

int n;
bool arr[16];

void dfs(int k) {
    if(k==n) {
        for(int i=0;i<n;i++){
            if(arr[i]) printf("%d ",i+1);
        }
        printf("\n");
        return;
    }

    //进行两种选择
    arr[k] = false;
    dfs(k+1);
    arr[k] = true;
    dfs(k+1);
}

int main() {
    cin>>n;
    dfs(0);

    return 0;
}

题解二

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

int n;
int arr[16];

void dfs(int i,int k) {
    if(k>0) {
        for(int j=0; j<k; j++) {
            printf("%d ",arr[j]);
        }
    }
    printf("%d\n",i);

    arr[k]=i;
    if(k==n-1) return;
    for(int j=i+1; j<=n; j++) {
        dfs(j,k+1);
    }
}

int main() {
    cin>>n;
    printf("\n");
    for(int i=1; i<=n; i++) {
        dfs(i,0);
    }

    return 0;
}

标题：	AcWing-92-递归实现指数型枚举
链接：	https://www.fightingok.cn/detail/29
更新：	2022-09-18 22:32:41
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可