LeetCode.46. 全排列(回溯法入门)

写在前面：

题目链接：LeetCode.46. 全排列
编程语言：C++
题目难度：中等

一、题目描述

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例3：

输入：nums = [1]
输出：[[1]]

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

二、解题思路

2.1 回溯法

我们再次用 树状思维逻辑，从根出发，叶子节点为结果集之一
示例：

这个树像是做一个减法：
从这个集合里，不断的取出一个数字，再将这个数字从当前集合中删除掉，剩下的元素做下一次的可选值

这里我曾经想用一个set 保存这些值，每选一个数字，就从set 中 erase 掉这个数字，然后把这个 set 再做下一次选择的集合，问题是每次需要初始化为一个 全集，似乎有点麻烦，这样我们换一种思路：

维护一个 vector isUsed 数组，开始都初始化为 false ,代表每个元素都没有用过，每当选择其中一个元素，将该元素置为 true 代表用过了，下一次选择的时候，只选择 值为 false 的元素

这里的下一次当然要使用递归，一直递归到 结果 刚好 == nums.size() , 表示这一组排列组合已经完成了，那么如何回溯呢？

代码实现：

class Solution {
public:
    vector<vector<int>> vctResult;//所有结果集
    vector<int> vctTemp;//子集
    void back(vector<int>& nums, vector<bool>& isUsed)
    {
        if(vctTemp.size() == nums.size())
        {
            vctResult.push_back(vctTemp);
            return;
        }
        for(int i = 0; i < nums.size();i++)
        {
            if(isUsed[i] == false)
            {
                vctTemp.push_back(nums[i]);//选择该数字
                isUsed[i] = true;
                back(nums, isUsed);//递归继续往下选择
                isUsed[i] = false;//回溯
                vctTemp.pop_back();
            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> isUsed(nums.size(), false);//每个元素的使用情况
        back(nums, isUsed);
        return vctResult;
    }
};
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

其实回溯代码也是有一个套路和模板的大致样子的，例如上述题目：

result //结果
def backtrack(路径, 选择列表):
    if 满足结束条件:
        reslut.push_back(结果集)
        return
    
    for 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择
1
2
3
4
5
6
7
8
9
10

三、完整代码

class Solution {
public:
    vector<vector<int>> vctResult;//所有结果集
    vector<int> vctTemp;//子集
    void back(vector<int>& nums, vector<bool>& isUsed)
    {
        if(vctTemp.size() == nums.size())
        {
            vctResult.push_back(vctTemp);
            return;
        }
        for(int i = 0; i < nums.size();i++)
        {
            if(isUsed[i] == false)
            {
                vctTemp.push_back(nums[i]);//选择该数字
                isUsed[i] = true;
                back(nums, isUsed);//递归继续往下选择
                isUsed[i] = false;//回溯
                vctTemp.pop_back();
            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> isUsed(nums.size(), false);//每个元素的使用情况
        back(nums, isUsed);
        return vctResult;
    }
};
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

运行结果：