题目描述

排列数字

样例

3

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

算法1

用 path 数组保存排列，当排列的长度为 n 时，是一种方案，输出。
用 state 数组表示数字是否用过。当 state[i] 为 1 时：i 已经被用过，state[i] 为 0 时，i 没有被用过。
dfs(i) 表示的含义是：在 path[i] 处填写数字，然后递归的在下一个位置填写数字。
回溯：第 i 个位置填写某个数字的所有情况都遍历后， 第 i 个位置填写下一个数字。

建议手动模拟一遍，注意for里面的i是多少，退出dfs不仅靠return,循环结束即意味着函数结束！！！

参考文献

原文链接：https://www.acwing.com/solution/content/30988/

C++ 代码

#include<iostream>
using namespace std;

const int N =10;

int n;
int path[N];//保存序列
bool st[N];//数字是否被用过

void dfs(int u){

    if(u==n){//数字填完了，输出
        for(int i=0;i<n;i++) printf("%d ",path[i]); //输出方案
        puts("");
        return;
    }

    for(int i=1;i<=n;i++)//空位上可以选择的数字为:1 ~ n
    if(!st[i]){//如果数字 i 没有被用过
        path[u]=i;//放入空位
        st[i]=true;//数字被用，修改状态
        dfs(u+1);//填下一个位
        st[i]=false;//回溯，取出 i
    }

}

int main(){
    cin>>n;

    dfs(0);

    return 0;
}