一本通-1317：【例5.2】组合的输出（回溯）

【题目描述】 排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r≤n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。

现要求你用递归的方法输出所有组合。

例如n＝5，r＝3，所有组合为：1 2 3   1 2 4   1 2 5   1 3 4   1 3 5   1 4 5   2 3 4   2 3 5   2 4 5   3 4 5

【输入】 一行两个自然数n、r(1<n<21，1≤r≤n)。

【输出】 所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。

【输入样例】 5 3

【输出样例】   1  2  3   1  2  4   1  2  5   1  3  4   1  3  5   1  4  5   2  3  4   2  3  5   2  4  5   3  4  5

---

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <set>
#include <algorithm>

using namespace std;

int n, m;
//vector<bool> used(21, false);
vector<int> res;

void DFS(int k)
{
    if (res.size() > m || res.size() + n - k + 1 < m)
        return;

    if (k == n + 1) {
        setiosflags(ios::right);
        for (int index = 0; index < m; ++index) {
            cout << setw(3) << res[index];
        }
        cout << endl;
        return;
    }

    res.push_back(k); //选择x
    DFS(k + 1);
    res.pop_back(); //恢复原状
    //不选择
    DFS(k + 1);
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;

    DFS(1);

    return 0;
}

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <set>
#include <algorithm>

using namespace std;

int n, m;
vector<bool> used(25, false);
vector<int> res(25);

void DFS(int k)
{
    if (k == m + 1) {
        setiosflags(ios::right);
        for (int index = 1; index <= m; ++index) {
            cout << setw(3) << res[index];
        }
        cout << endl;
        return;
    }

    for (int i = res[k - 1]; i <= n; ++i) {
        if (!used[i]) {
            res[k] = i;
            used[i] = true;

            DFS(k + 1);

            used[i] = false;
        }
    }
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;

    res[0] = 1;
    DFS(1);

    return 0;
}

按照一本通第一种回溯框架写，比较固定一些：

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<bool> used(25, false);
vector<int> res(25);

void DFS(int k)
{
    for (int i = res[k - 1]; i <= n; ++i) {
        if (!used[i]) {
            used[i] = true;
            res[k] = i;

            if (k == m) { //输出结果
                setiosflags(ios::right);
                for (int index = 1; index <= m; ++index) {
                    cout << setw(3) << res[index];
                }
                cout << endl;
            }
            else DFS(k + 1);

            used[i] = false;
        }
    }
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    res[0] = 1;
    DFS(1);

    return 0;
}