解题思路

从 1~n 中挑出 r 个数进行排列，按字典序从小到大输出所有排列。

思路：回溯。

把排列看成 r 个位置，从第一个位置开始填：

1. 对每个位置，尝试放 1~n 中还没用过的数
2. 放好后标记已用，递归填下一个位置
3. 填满 r 个位置就输出
4. 回溯恢复标记，试下一个数

为什么要回溯（恢复标记）？ 第 s 个位置试完数字 1 后，还要试数字 2，所以用完要释放标记。

举例：n=5，r=2

• 第 1 个位置放 1，第 2 个位置可以放 2、3、4、5
• 输出 1 2、1 3、1 4、1 5
• 然后第 1 个位置放 2……依次类推

因为每次从小到大试数字，输出自然就是字典序从小到大。

参考代码

#include <iostream>
using namespace std;

int n, r, book[10], a[10];

void pl(int s) {
    if (s == r + 1) {  // 填满 r 个位置
        for (int i = 1; i <= r; i++) cout << a[i] << " ";
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (book[i] == 0) {  // 还没用过
            a[s] = i;
            book[i] = 1;
            pl(s + 1);
            book[i] = 0;  // 回溯
        }
    }
}

int main() {
    cin >> n >> r;
    pl(1);
    return 0;
}

复杂度分析

• 时间复杂度：O(P(n,r))，即排列数
• 空间复杂度：O(R)，路径和标记数组