算法

回溯 全排列问题

题目

对于一个数集，穷举其所有可能的排列顺序在很多地方都有应用。这里引入比较简单的全排列问题：https://www.luogu.com.cn/problem/P1706 全排列一般使用的是递归回溯的方法进行编写。

题解

首先我们需要一个递归函数，实际转换成了回溯问题。
这里是函数声明，形参好多，不过每个都挺重要的：

1
2

void backtrack(std::vector<int> &state, const std::vector<int> &nums, std::vector<bool> &selected,
               std::vector<std::vector<int>> &res);

这里简单介绍下各个参数：

  • vector<int> &state 状态数组，这里放置现在选择的元素
  • const vector<int> &choices 候选集合，输入数组的所有元素
  • vector<bool> &selected 这里的 selected[i] 表示 choices[i] 是否已被选择，并基于它实现剪枝操作
  • vector<vector<int>> &res 结果数组，保存结果
    首先，我们遍历候选集合的每一个元素，将每个元素依次添加到状态数组末尾，每次添加后都递归一次。这里就像树一样有多个分支。每当分支的元素数量和候选集合一样说明一个新的结果出现。这里使用了一个布尔数组来防止出现重复的元素，并在递归的过程进行剪枝，优化算法效率。

递归结束条件

一般在每个递归函数中，最先要写的是停止递归开始回溯的条件，这里的回溯条件较为简单，主要是添加结果并返回。

1
2
3
4
5

if (state.size() == choices.size())
{
    res.push_back(state);
    return;
}

穷举循环

穷举问题一般都伴随一个循环来对每一种可能进行穷举，这里遍历所有可能：

1

for (int i = 0; i < choices.size(); i++)

显然，在每一次再进行递归可能会出现重叠的情况，这里就需要存储已经被筛选的元素的布尔数组进行判断。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

for (int i = 0; i < choices.size(); i++)
{
    int choice = choices[i];
    // 剪枝：不允许重复选择元素
    if (!selected[i])
    {
        selected[i] = true;
        state.push_back(choice);
        // 进行下一轮选择
        backtrack(state, choices, selected, res);
        // 回退：撤销选择，恢复到之前的状态
        selected[i] = false;
        state.pop_back();
    }
}

在确认 selected[i] 为 false 后，说明该元素没有被选择，可以进行后续步骤：

  • 标记已被选择
  • 将元素插入状态数组末尾
  • 递归当前函数
  • 将该元素标记撤销
  • 删除该元素

显然当每一次元素数量达到的时候才会向前回溯。这里的方式是自洽合适的。

回溯代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

void backtrack(vector<int> &state, const vector<int> &choices, vector<bool> &selected, vector<vector<int>> &res)
{
    if (state.size() == choices.size())
    {
        res.emplace_back(state);
        return;
    }

    for (int i = 0; i < choices.size(); i++)
    {
        int choice = choices[i];
        // 剪枝：不允许重复选择元素
        if (!selected[i])
        {
            selected[i] = true;
            state.push_back(choice);
            // 进行下一轮选择
            backtrack(state, choices, selected, res);
            // 回退：撤销选择，恢复到之前的状态
            selected[i] = false;
            state.pop_back();
        }
    }
}

vector<vector<int>> permutationI(vector<int> nums)
{
    vector<int> state;
    vector<bool> selected(nums.size(), false);
    vector<vector<int>> res;
    backtrack(state, nums, selected, res);
    return res;
}

向外包装

但是该函数的参数实在是太多了，而且很多都预先是不变（为空的）。如果能再外包装一层调用函数显然更好。 在前面参数中，state、res 应该是空数组，而 selected 是一个元素数量和候选集合相同且均为 false 的布尔数组。
在此基础上构造函数，现在只剩下 choices 是我们真正会发生变化的参数了：

1
2
3
4
5
6
7
8

vector<vector<int>> permutationI(vector<int> nums)
{
    vector<int> state;
    vector<bool> selected(nums.size(), false);
    vector<vector<int>> res;
    backtrack(state, nums, selected, res);
    return res;
}

主函数——输入输出

显然上面只是全排列的核心算法，还需要处理输入输出才能解决本题：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

int main()
{
    int n;
    vector<int> nums;
    vector<vector<int>> res;
    cin >> n;
    for (int i = 1; i <= n; i++)
        nums.emplace_back(i);
    res = permutationI(nums);

    for (auto iter : res)
    {
        for (int i = 0; i < iter.size(); i++)
        {
            cout << "    " << iter[i];
        }
        if (iter != *(res.end() - 1))
            cout << endl;
    }
}

没什么好讲的，只不过这里的用例空格个数和位置需要弄清楚。挺难绷的，原本结果是对的，但是卡在输出格式上全 WA 好几次才 AC。

参考资料

  1. hello 算法 13.2 全排列问题
萌ICP备20241614号