P1706 全排列问题——题解

解题思路

从左到右确定排列的每一位。当前位依次尝试 $1$ 到 $n$ 中尚未使用的数字，递归处理下一位；返回时撤销使用标记。由于每层都按数字从小到大尝试，输出天然是字典序。

正确性说明

搜索的每条完整路径选择了 $n$ 个互不相同的数字，因此对应一个合法排列；任意合法排列都能按照自身各位选择形成唯一的一条搜索路径，所以不会遗漏或重复。

复杂度分析

共有 $n!$ 个排列，输出和搜索时间为 $O(n\cdot n!)$，辅助空间 $O(n)$。

易错点

必须使用 setw(5) 保证场宽；回溯后要清除 used[x]。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int n,a[10]; bool used[10];
void dfs(int dep){
    if(dep>n){
        for(int i=1;i<=n;i++) cout<<setw(5)<<a[i];
        cout<<'\n'; return;
    }
    for(int x=1;x<=n;x++) if(!used[x]){
        used[x]=true; a[dep]=x;
        dfs(dep+1);
        used[x]=false;
    }
}
int main(){cin>>n;dfs(1);return 0;}

#include <bits/stdc++.h> using namespace std; int n,a[10]; bool used[10]; void dfs(int dep){ if(dep>n){ for(int i=1;i<=n;i++) cout<<setw(5)<<a[i]; cout<<'\n'; return; } for(int x=1;x<=n;x++) if(!used[x]){ used[x]=true; a[dep]=x; dfs(dep+1); used[x]=false; } } int main(){cin>>n;dfs(1);return 0;}