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

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

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

作者：

lovebecky , 2019-01-19 11:34:31 , 所有人可见 , 阅读 32998

286

188

题目描述

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

输入格式

输入一个整数n。

输出格式

每行输出一种方案。

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

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

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

数据范围

1≤n≤15

输入样例：

输出样例：

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

填坑，从填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

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

包子云 2022-03-23 10:57

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

ℱ. 2025-02-21 09:15 · 河南

#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

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

王鹏宇 2023-01-17 18:24

状压非递归太妙了

晔_8 2022-12-09 11:24

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

uuuuu 2022-12-18 14:23

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

微凉_9 2023-01-25 18:24

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

不与世俗纷争 2023-12-28 19:41

我也不懂

acwing_jmx 2024-01-20 09:36

第二个代码不需要开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

# 想知道为什么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

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;
}