题目描述

两种思路
思路1 依次枚举每个位置放哪个数
思路2 依次枚举每个数放到哪个位置

思路1

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10;

int n;
int state[N]; //0表示还没放数（变量定义为全局变量，初值一定是0，局部变量初值为随机值）
bool used[N]; //true表示用过，false表示还未用过

void dfs(int u) //往位置u放置数字
{
    if(u > n) //某一分支走到头时，输出边界。u==4说明前三个位置放满了
    {
        for(int i = 1; i <= n; i++) printf("%d ", state[i]); //打印方案
        puts("");

        return;
    }

    //依次枚举每个分支，即当前位置可以填哪些数
     for(int i = 1; i <= n; i++) //i代表的是数字，u代表的是位置
         if(!used[i])
         {
             state[u] = i;
             used[i] = true;
             dfs(u+1); //继续往下一个位置放置没放过的数字

             state[u] = 0; //恢复现场对应树状图输出某一分支结果后回溯直上一级节点
             used[i] = false; //要恢复默认状态
         }
}

int main()
{
    cin >> n;
    dfs(1);

    return 0;
}

思路2

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10;

int n;
int loca[N];

void dfs(int u) //u这个数填到哪个位置，u代表的是数字
{
    if(u>n)
    {
        for(int i = 0; i < n; i++)
        {
            printf("%d ", loca[i]);
        }
        printf("\n");
    }

    for(int i = 0; i < n; i++) //每次都依次循环每个位置
    {
        if(!loca[i])
        {
            loca[i] = u;
            dfs(u+1);

            loca[i] = 0;
        }
    }
}

int main()
{
    cin >> n;

    dfs(1);

    return 0;
}