---
title: "全排列"
created: 2025-11-28
tags:
  - 算法
---

# 全排列

## 题目 [递归实现排列型枚举](https://www.acwing.com/problem/content/96/)

![[image-1631d1a8.png]]

## 思路分析

全排列问题可以用`next_permutation`直接做next\_permutation

使用递归的话 也就是枚举每个位置应该放哪个数

![[image-9275171c.png]]

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

vector<int> a;

int n;

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++){

        a.push_back(i);

    }

    do{

        for(int num:a){

            cout<<num<<" ";

        }

        cout<<endl;

    }while(next_permutation(a.begin(),a.end()));

    return 0;

}
```

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=10;

int state[N];//0表示还没放数 1~n表示放了哪个数

int used[N];//true用过 false没用过

int n;

void dfs(int u){

    if(u>n){

        for(int i=1;i<=n;i++)

            cout<<state[i]<<" ";

        cout<<endl;

        return;

    }

    for(int i=1;i<=n;i++){

        if(!used[i]){

            state[u]=i;

            used[i]=true;

            dfs(u+1);

            state[u]=0;

            used[i]=false;

        }

    }

}

int main()

{

    cin>>n;

    dfs(1);//两个参数 当前位置u 每个位置是几的state 另为防止重复 记录某数用过没 used

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[集合询问|集合询问]] 🏠 [[00-刷题理模型]] ➡️ [[五塔|五塔]]