一. 题目

二. 理论

三. 代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=10;

int n;

class Search
{
public:
    int path[N];
public:
    void initIO()
    {
        // 关闭输入输出缓存，使效率提升
        ios::sync_with_stdio(false);
        // 解除cin和cout的默认绑定，来降低IO的负担使效率提升
        cin.tie(nullptr);
        cout.tie(nullptr);
    }

    Search()
    {
        initIO();
        fill(path, path+N, 0);
    }

    /**
     * 搜索函数
     * @param u 表示当前在第几层，最开始在第0层，当u==n时，说明到达最后一层
     * @param state 数字是否已选的状态，二进制位为1表示当前数字已选
     */
    void dfs(int u, int state)
    {
        if(u==n)
        {
            for(int i=0;i<n;++i)
                cout<<path[i]<<" ";
            cout<<endl;
            return;
        }

        for(int i=1;i<=n;++i)
            if(((state>>(i-1))&1)==0)//判断i数字是否为1，为1表示已经使用则跳过
            {
                path[u]=i;//优于每次都是赋值，所以path不用回溯
                dfs(u+1, state|(1<<(i-1)));//第二个参数，
                // i-1二进制位表示第i个数字，写成参数的形式不用回溯，因为并没有赋值给state
            }
    }
}s;

int main()
{
    cin>>n;
    s.dfs(0, 0);
}