非递归实现

2^n 个选择。我们只选 m 个。

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;

int lowbit(int x) {
    return x = x & (x - 1);
}
int bitCount(int x) {
    int res = 0;
    while (x) {
        res ++;
        x = lowbit(x);
    }
    return res;
}

int main() {
    cin >> n >> m;
    vector<vector<int>> res;
    int k = 0;
    for (int i = 0; i < 1 << n; i ++) {
        if (bitCount(i) == m) {
            vector<int> path;
            for (int j = 1; j <= n; j ++) {
                if (i >> (j - 1) & 1) {
                    path.push_back(j);
                }
            }
            res.push_back(path);
        }
    }
    sort(res.begin(), res.end());
    for (auto v : res) {
        for (auto x : v) {
            cout << x <<' ';
        }
        cout << endl;
    }
    return 0;
}