P4917 N个数的全排列（入门）

解题思路

第一步，理解题意。 给出n个互不相同的正整数，它们已经按升序排好，我们要输出这n个数的所有全排列，并且每个数只能使用一次。输出顺序要优先输出较小的数字，也就是按字典序从小到大输出。例如输入7 9 12，第一行是7 9 12，最后一行是12 9 7。

第二步，深度优先搜索。 由于输入已经升序，我们直接从小到大选数字即可。用一个数组ans存放当前排列，用used标记某个数是否已被选过。dfs(dep)表示已经确定了dep个位置：如果dep等于n，就把当前排列输出一行；否则，从下标0到n-1从小到大找第一个还没被用的数字放进第dep个位置，然后递归。

第三步，回溯。 递归回来以后要把used标记还原，这样同一个数字可以被不同的位置使用。因为每个数互不相同，所以每个排列都不同，不会重复。

第四步，和降序全排列对比。 另一道类似的题目是先排序再从大到小选，输出降序排列；这道题输入已经升序、从小到大选，输出升序排列。两者的搜索框架完全一样，只是枚举数字的顺序相反。

第五步，验证样例。 输入3和7 9 12，从小到大选会依次输出7 9 12、7 12 9、9 7 12、9 12 7、12 7 9、12 9 7，正好是字典序从小到大，和样例一致。n最大9，排列总数9!约36万，完全可以在时限内输出。

参考代码

// 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 = 0; i < n; 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];
    dfs(0);
    return 0;
}

复杂度分析

n个数一共有n!种排列，每种排列输出n个数，时间复杂度O(n·n!)。n最大9，9!约36万，即使每个排列都输出一遍也很快。空间上用了ans和used等几个数组，空间复杂度O(n)。