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

题目描述

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

输入格式

输出格式

每行输出一种方案。

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

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

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

数据范围

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

输入样例

3

输出样例

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

题目分析

我们可以用一个 n n n 位二进制数来表示一个有 n n n 个元素的集合中的一种选取情况。譬如在集合 { 1 , 2 , 3 , 4 , 5 } \{1,2,3,4,5\} {1,2,3,4,5} 中， 10110 10110 10110 可代表选 1 , 3 , 4 1,3,4 1,3,4 的情况。而为了得到所有的情况，我们可以枚举所有的二进制数。

代码 (枚举二进制数)：

#include <iostream>
using namespace std;
int n, num[20];

int main(){<!-- -->
    cin >> n;
    for (int i = 0; i < n; i ++) num[i] = i + 1;
    
    for (int i = 0; i < 1 << n; i ++){<!-- -->
        for (int j = 0; j < n; j ++)
            if (i >> j & 1)
                cout << num[j] << " ";
        cout << endl;
    }
}

当然，我们也可以用递归方式实现指数型枚举。对于每一个数，它有两种选择：选或不选。每次递归分别尝试两条分支，将尚未确定的整数数量减 1 1 1，从而转化为规模更小的同类问题。

代码 (递归)：

#include <iostream>
#include <vector>
using namespace std;
int n;
vector <int> num;

void work(int x){<!-- -->
    if (x == n + 1){<!-- -->
        for (int i = 0; i < num.size(); i ++)
            cout << num[i] << " ";
        cout << endl;
        return;
    }
    num.push_back(x);  //选第x个数
    work(x + 1);
    num.pop_back();  //回溯,不选第x个数
    work(x + 1);
}

int main(){<!-- -->
    cin >> n;
    work(1);
}