AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

AcWing 92. 递归实现指数型枚举    原题链接    简单

作者: 作者的头像   lovebecky ,  2019-01-19 11:34:31 ,  所有人可见 ,  阅读 33223


289


188

题目描述

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

输入格式

输入一个整数n。

输出格式

每行输出一种方案。

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

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

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

数据范围

1≤n≤15

输入样例:

3

输出样例:


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

引例:如果题目不要求输出方案必须升序

填坑,从填1个坑到填n个坑。
坑可以随便填,比如第1个坑选了2之后,第2个坑可以填1(非升序),也可以填3(升序)

#include <iostream>
using namespace std;
typedef long long ll;

int n;
int a[20];
bool vis[20];

// 一共tar个坑,当前枚举到第pos个坑
void dfs(int pos, int tar) {
    if (pos == tar + 1) {
        for (int i = 1; i <= tar; i ++ ) cout << a[i] << " ";
        cout << endl;
        return ;
    }

    // 选数填坑,选择的数范围是1~n
    for (int i = 1; i <= n; i ++) {
        if (!vis[i]) {
            vis[i] = true; a[pos] = i;
            dfs (pos + 1, tar);
            vis[i] = false;
        }
    }
}

int main() {
    cout << endl; // 不取
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        dfs(1, i);
    return 0;
}

所有升序方案

依旧是填坑,从填1个坑到填n个坑。
和上面不同的是,上面是第1个坑选了2之后,第2个坑还可以从2之前的数开始填坑,现在是第1个坑选了2之后,第2个坑只能从大于2的数里选了。
即,当前的坑pos处填了num,则填下一个坑pos+1时,只能从大于num的数里选择填坑。

解决办法:dfs里加一个start,选数的时候,只能从start之后的数里面选择

总结:dfs需要四个变量记录当前状态:
当前位于的坑pos,当前可以选的最小数字start,当前的目标总坑数tar,当前已经填的坑数组a[]。

#include <iostream>
using namespace std;

int n;
int a[20];
bool vis[20];

// 当前枚举到第pos个坑, 上一个坑填的是start-1,这次只能从start开始找数填, 一共要填tar个坑
void dfs(int pos, int start, int tar) {
    if (pos == tar + 1) {
        for (int i = 1; i <= tar; i ++ ) cout << a[i] << " ";
        cout << endl;
        return ;
    }

    // 选数填坑,选择的数范围是start~n
    for (int i = start; i <= n; i ++) {
        if (!vis[i]) {
            vis[i] = true; a[pos] = i;
                dfs (pos + 1, i + 1, tar);
            vis[i] = false;
        }
    }
}

int main() {
    cout << endl;
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        dfs(1, 1, i);
    return 0;
}

二进制优化1:

用一个二进制数表示选了哪些数,替代之前的a[20]数组
其中 state |= 1 << (i - 1) 代表状态的改变,选了i这个数
state ^= 1 << (i - 1) 代表状态的还原,还原没选i这个数的状态

#include <iostream>
using namespace std;

int n;
bool vis[20];

void dfs(int pos, int start, int tar, int state) {
    if (pos == tar + 1) {
        for (int j = 0; j < n; j ++ ) {
            if (state >> j & 1) cout << j + 1 << " ";
        }
        cout << endl;
        return ;
    }

    for (int i = start; i <= n; i ++) {
        if (!vis[i]) {
            vis[i] = true; state |= 1 << (i - 1);
                dfs (pos + 1, i + 1, tar, state);
            vis[i] = false;state ^= 1 << (i - 1);
        }
    }
}

int main() {
    cout << endl;
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        dfs(1, 1, i, 0);
    return 0;
}

状态压缩非递归

状态压缩的特性:可以枚举所有选与不选的情况

题目要求的结果是2^n个
这2^n个选择情况,对应于一个n位的2进制数的各个位取0或取1的情况。
例中n=3,即
000 -> \n
001 -> 1
010 -> 2
100 -> 3
011 -> 1 2
101 -> 1 3
110 -> 2 3
111 -> 1 2 3

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    // state 是每一个状态
    for (int state = 0; state < 1 << n; state ++ ) {
        // 用指针j遍历二进制数state中的每一位
        for (int j = 0; j < n; j ++ ) {
            if (state >> j & 1) cout << j + 1 << " ";
        }
        cout << endl;
    }
    return 0;
}

状态压缩递归:(学习自yxc大神)

#include <iostream>
using namespace std;

int n;

// u是当前枚举到的数,state是二进制数记录哪些数被选
void dfs(int u, int state) {
    if (u == n) {
        for (int i = 0; i < n; i ++)
            if (state >> i & 1)
                cout << i + 1 << " ";
            cout << endl;
        return ;
    }

    dfs (u + 1, state);  // 不用u这个数
    dfs (u + 1, state | (1 << u)); // 用u这个数
}

int main() {
    cin >> n;
    dfs(0, 0);
    return 0;
}

60 评论


用户头像
凉城凉忆   2022-03-11 17:27      9    踩      回复

只想说大佬牛逼,有个小小的看法,那个 “所有升序方案” 里面的那个vis数组其实可以去掉,start的每次取值+1,已经保证了不会有重复的取值了

用户头像
包子云   2022-03-23 10:57      1    踩      回复

我也是!刚刚写完组合枚举,发现怎么他就不用判重数组,测试了下,这个也不用!

用户头像
ℱ.   2025-02-21 09:15 · 河南      1    踩      回复

#include [HTML_REMOVED]
using namespace std;

int n;
int a[20];

// 当前枚举到第pos个坑, 上一个坑填的是start-1,这次只能从start开始找数填, 一共要填tar个坑
void dfs(int pos, int start, int tar) {
if (pos == tar + 1) {
for (int i = 1; i <= tar; i++) cout << a[i] << ” “;
cout << endl;
return;
}

// 选数填坑,选择的数范围是start~n
for (int i = start; i <= n; i++) {
    a[pos] = i;
    dfs(pos + 1, i + 1, tar);
}

}

int main() {
cout << endl;
cin >> n;
for (int i = 1; i <= n; i++)
dfs(1, 1, i);
return 0;
}


用户头像
听见早安   2022-03-04 21:45      7    踩      回复

在第二块也就是还没有用到二进制的时候,虽然看起来简单,但其实深究,感觉真是太神奇了,每一步都设计的刚到位,也许,这就是算法的魅力吧,看了好久,才摸索到一二,感觉还是没有完全懂


用户头像
王鹏宇   2023-01-17 18:24      4    踩      回复

状压非递归太妙了


用户头像
晔_8   2022-12-09 11:24      4    踩      回复

为什么一定需要恢复现场啊?不恢复现场并不影响答案啊?

用户头像
uuuuu   2022-12-18 14:23      1    踩      回复

同问,我看y总被覆盖了也没懂

用户头像
微凉_9   2023-01-25 18:24      3    踩      回复

可以不恢复现场,y总视频中说是为了让过程更清晰

用户头像
不与世俗纷争   2023-12-28 19:41      1    踩      回复

我也不懂


用户头像
acwing_jmx   2024-01-20 09:36      2    踩      回复

第二个代码不需要开tar参数吧,只需要每次输出枚举完成的pos个数就行了

所以两个参数就行:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {    
    static int n;

    static boolean[] st = new boolean[10];
    static int[] res = new int[10];

    static void dfs(int u, int start) {
        for (int k = 0; k < u; k ++) System.out.print(res[k] + " ");
        System.out.println();

        for (int i = start; i <= n; i ++) {
            if (!st[i]) {
                res[u] = i;
                st[i] = true;
                dfs(u + 1, i + 1);
                st[i] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        dfs(0, 1);
    }
}

用户头像
糖醋拐杖_   2023-10-29 17:40      1    踩      回复

# 想知道为什么AC不了

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

int n;

int cf(int u)
{
    int temp = 2;
    if (u == 1) return temp;
    else 
    {
        for (int i = 1;i < u;i++)
        {
            temp *= 2;
        }
    }
    return temp;
}


int main()
{
    cin >> n;
    int m = cf(n);
    for (int i = 1;i < m;i++)
    {
        int temp = i;
        int cnt = 1;
        while (temp)
        {
            if (temp & 1) cout << cnt<< " ";
            temp >>= 1;
            cnt++;
        }
        puts("");
    }
    return 0;
}

用户头像
小王今天吃什么   2022-11-17 15:37      1    踩      回复

tql


用户头像
001_13   2025-03-05 14:04 · 山东         踩      回复

#include [HTML_REMOVED]
using namespace std;
typedef long long ll;

int n;
int a[20];
bool vis[20];

// 一共tar个坑,当前枚举到第pos个坑
void dfs(int pos, int tar) {
if (pos == tar + 1) {
for (int i = 1; i <= tar; i++)
cout << a[i] << ” “;
cout << endl;
return;
}

// 选数填坑,选择的数范围是1~n
for (int i = 1; i <= n; i++) {
    if (!vis[i]&&i>a[pos-1]) {
        vis[i] = true; a[pos] = i;
        dfs(pos + 1, tar);
        vis[i] = false;
    }
}

}

int main() {
cout << endl; // 不取
cin >> n;
for (int i = 1; i <= n; i++) 59
dfs(1, i);
return 0;
}这个可以吗,实现了大小排序


用户头像
Dawn_89   2024-11-25 11:44         踩      回复

状态压缩非递归,简直米奇妙妙屋


用户头像
佑佑变强日记   2024-04-10 08:57         踩      回复

请问蓝桥杯比赛时最后多空一行有问题吗


用户头像
20yxzeng   2024-01-02 13:40         踩      回复
#include <bits/stdc++.h>

int buff[1024], tot;

void dfs(int n, int pos){
    for(int i = 0; i < tot; i++)
        printf("%d ", buff[i]);
    printf("\n");
    for(int i = pos + 1; i <= n; i++){
        buff[tot++] = i;
        dfs(n, i);
        tot--;
    }
}

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

用户头像
chaomianwang   2023-12-12 21:55         踩      回复

好棒!lao!


用户头像
11_058   2023-10-11 21:54         踩      回复

状态压缩非递归那里,为什么j<n?


用户头像
宝山   2023-04-05 16:15         踩      回复

大佬,我这个为什么打印不出来东西:

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

const int N = 16;

int n;
int st[N];

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

int main()
{
    scanf("%d", &n);
    dfs(1);
    return 0;
}
用户头像
又被码住了   2024-03-11 16:48         踩      回复

条件是st[i]==1


用户头像
Bailey   2023-03-23 20:23         踩      回复

for (int state = 0; state < 1 << n; state ++ ) 这一句怎么理解

用户头像
m_math   2023-09-08 15:25         踩      回复

枚举所有取或不取的状态

用户头像
Seymour   2024-04-27 10:44    回复了 m_math 的评论         踩      回复

为什么不能从一开始枚举


用户头像
稳如   2023-02-06 10:48         踩      回复

(如果是学习交流注意申明,小心版权问题)这是原创吗,我在csdn上看到基本一摸一样的,如果是本人当我没说。https://blog.csdn.net/zhaohaibo_/article/details/86538769


用户头像
稳如   2023-02-06 10:45         踩      回复

这是原创吗,我在csdn上看到基本一摸一样的。(如果是学习交流注意申明,小心版权问题 )
https://blog.csdn.net/zhaohaibo_/article/details/86538769


用户头像
TaTaTa110   2023-01-28 20:25         踩      回复

第一个不能ac

用户头像
环辛四烯   2023-03-12 11:11         踩      回复

都说了是非升序的


用户头像
xsxsxs   2023-01-19 23:14         踩      回复

%


用户头像
Tom__   2023-01-02 21:04         踩      回复

状态压缩非递归更快呀


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息