P4916 降序优先的全排列（入门）

解题思路

第一步，理解题意。 给出n个互不相同的正整数，要把它们的所有全排列都输出出来。输出顺序有讲究：要先输出较大的数字，也就是按照字典序从大到小的顺序输出。例如输入9 7 12，第一个输出的排列是12 9 7，最后一个才是7 9 12。

第二步，先排序。 题目给的数字可能是乱序的，比如9 7 12。我们先把它们从小到大排序，排序后是7 9 12，然后再用从大到小选数字的方式做深度优先搜索，这样生成的排列就正好是字典序从大到小。

第三步，深度优先搜索。 用一个数组ans存当前已经选好的数字，用used数组标记某个数字是否已经被选。dfs(dep)表示已经选了dep个数字：如果dep等于n，就输出这一行排列；否则，从下标n-1到0倒着枚举还没被选的数字，这样先选大的，选进来继续递归。

第四步，回溯。 递归返回后要把used标记清掉，让这个数字可以被别的位置再次使用。因为n最大只有9，最多9!约36万种排列，输出量不大。

第五步，验证样例。 输入3和9 7 12，排序后是7 9 12，倒序选择会依次输出12 9 7、12 7 9、9 12 7、9 7 12、7 12 9、7 9 12，和样例完全一致。插入排序是自己写的小排序，因为n很小，任何排序方法都可以。

参考代码

// 降序优先的全排列：先升序排序，再从大到小选数构造排列
#include <iostream>
using namespace std;
int a[12];
int ans[12];
int used[12];
int n;
void dfs(int dep) {
    if (dep == n) {
        for (int i = 0; i < n; i++) {
            if (i) cout << ' ';
            cout << ans[i];
        }
        cout << endl;
        return;
    }
    for (int i = n - 1; i >= 0; i--) { // 下标从大到小，先选大的数字
        if (used[i]) continue;
        used[i] = 1;
        ans[dep] = a[i];
        dfs(dep + 1);
        used[i] = 0;
    }
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    // 插入排序：把a按从小到大排好
    for (int i = 1; i < n; i++) {
        int cur = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > cur) { a[j + 1] = a[j]; j--; }
        a[j + 1] = cur;
    }
    dfs(0);
    return 0;
}

复杂度分析

全排列一共有n!个，每个排列要输出n个数，所以总时间复杂度是O(n·n!)。n最大9，9!约36万，输出总量不大。空间上用了几个长度为n+1的数组，空间复杂度O(n)。由于n很小，这个搜索运行非常快。