递归解决全排列问题

顺序：按每一位搜索
递归思路：1.边界 2.递归 3.恢复现场

#include <iostream>

using namespace std;

const int N = 10;

int n;
int path[N]; // 记录路径
bool st[N]; // 记录当前数是否用过

void dfs(int u)
{
    // 递归思路：1.边界 2.递归 3.恢复现场
    if(u==n) // 1.边界
    {
        for(int i=0;i<n;i++) cout<<path[i]<<" ";
        cout<<endl;
        return ;
    }

    for(int i=1;i<=n;i++)
    {
        if(!st[i])  // 2. 递归
        {
            path[u]=i;
            st[i] = true;
            dfs(u+1);
            st[i] = false; // 3.恢复现场
        } 

    }
}

int main()
{
    cin>>n;
    dfs(0); // 搜索顺序：从第0位开始搜索

    return 0;
}

调用<algorithm>里的next_permutation()方法

next_permutation()给出一个序列在全排列中的下一个序列，到达全排列最后一个会返回false

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10;

int a[N];

int main()
{
    int n;
    cin >> n;
    for(int i=1;i<=n;i++) a[i] = i;
    do{
        for(int i=1;i<=n;i++) cout<<a[i]<<" ";
        cout<<endl;
    }while(next_permutation(a+1,a+1+n));

    return 0;
}