LeetCode.46. 全排列(回溯法入门)-Toy模板网

这篇具有很好参考价值的文章主要介绍了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 回溯法

我们再次用树状思维逻辑，从根出发，叶子节点为结果集之一
示例：
LeetCode.46. 全排列(回溯法入门)
这个树像是做一个减法：
从这个集合里，不断的取出一个数字，再将这个数字从当前集合中删除掉，剩下的元素做下一次的可选值

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

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

LeetCode.46. 全排列(回溯法入门)
这里的下一次当然要使用递归，一直递归到结果刚好 == 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;
    }
};

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

result //结果
def backtrack(路径, 选择列表):
    if 满足结束条件:
        reslut.push_back(结果集)
        return
    
    for 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

三、完整代码

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;
    }
};