题目描述

把 1~n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。

样例

输入样例:3

输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

算法1

(暴力搜索dfs)

思路是考虑n个位置,从第一个位置开始考虑,每个位置可以放哪些元素
u代表是在考虑第u个位置
这个题目跟组合型枚举题目不同
组合型枚举要求后续不能考虑前面已经选取的元素
排列型枚举可以考虑之前已经选过的元素

C++ 代码

#include<iostream>
#include<cstdio>
using namespace std;
int state[11]={0};
int visited[11]={0};

int n;

void dfs(int u)
{
    if(u>n)
    {
        for(int i=1;i<=n;i++)
        {
            printf("%d ",state[i]);
        }
        printf("\n");
    }
    for(int i=1;i<=n;i++)
    {
        if(!visited[i])
        {
            visited[i]=1;
            state[u]=i;
            dfs(u+1);
            visited[i]=0;
        }
    }
}
int main()
{
    cin>>n;
    dfs(1);
}