每日刷题|回溯法解决全排列问题
食用指南：本文为作者刷题中认为有必要记录的题目
前置知识：回溯法经典问题之组合
♈️今日夜电波：爱人错过—告五人
1:11 ━━━━━━️💟──────── 4:52
🔄 ◀️ ⏸ ▶️ ☰
💗关注👍点赞🙌收藏您的每一次鼓励都是对我莫大的支持😍
目录
回溯法的理解
💮 一、全排列
🌺二、全排列II
回溯法的理解
本文参考了一位大佬的题解，详细的介绍了回溯法：链接
上一篇刷题文： 回溯法经典问题之子集
记住一句话：for循环横向遍历，递归纵向遍历，回溯不断调整结果集。 这句话将从始至终贯穿我们对于以上问题的回溯解决办法。
💮 一、全排列
题目链接：46. 全排列
题目描述：
给定一个不含重复数字的数组
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] <= 10nums中的所有整数 互不相同
本题思路：
首先：采用经典的“回溯三部曲”：
1、定义两个全局变量，一个用来存放符合条件单一结果（path），一个用来存放符合条件结果的集合（result）。
2、回溯的主体，回溯终止条件。path保存一组数据，每次遍历到叶子节点，再插入到result中，并且回溯到上一个节点。
3、单层搜索的过程。for循环用来横向遍历，递归的过程是纵向遍历。
根据题意我们做出一定的改动：
我们额外定义一个bool类型的used用于确定每一个节点是否使用过，以此来解决重复插入的问题，并且也可以通过used对应的位置是否为false来确定是否进行后续操作。一句话概括就是：只有当used[i]==0时才去进行后续操作。
一图让你了解~以{1,2,3}为例
class Solution {
private:
vector<int> path;
vector<vector<int>> result;void trackback(vector<int>& nums,vector<bool>& used)
{if(path.size()==nums.size()){result.push_back(path);}for(int i=0;i<nums.size();i++){if(used[i]!=1){path.push_back(nums[i]);used[i]=1;trackback(nums,used);used[i]=0;path.pop_back();}}
}
public:vector<vector<int>> permute(vector<int>& nums) {path.clear();result.clear();vector<bool> used;used.resize(nums.size());sort(nums.begin(),nums.end());trackback(nums,used);return result;}
};🌺二、全排列II
题目链接：47. 全排列 II
题目描述：
给定一个可包含重复数字的序列
nums，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2] 输出： [[1,1,2],[1,2,1],[2,1,1]]
示例 2：
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示：
1 <= nums.length <= 8-10 <= nums[i] <= 10
本题思路：
本题实际上为上一题的拓展题目，基本上的思路跟上一题是的没什么区别的，但是由于此题中的元素是可以重复的，那我们就不能按照上一题只需要全部遍历一遍节点即可，在这里，我们需要加入剪枝操作，以此来解决重复选取问题。一句话概括就是：同一树枝上可以选取，但是同一树层上不可以选取！
即：添加这段判断语句{i>0&&nums[i-1]==nums[i]&&used[i-1]==0}来筛选重复的元素！
一图让你了解~以{1,1,2}为例
class Solution {
private:
vector<int> path;
vector<vector<int>> result;void trackback(vector<int>& nums,vector<bool>& used)
{if(path.size()==nums.size()){result.push_back(path);return;}for(int i=0;i<nums.size();i++){if(i>0&&nums[i-1]==nums[i]&&used[i-1]==0)continue;if (used[i] != 1){path.push_back(nums[i]);used[i] = 1;trackback(nums, used);used[i] = 0;path.pop_back();}}
}
public:vector<vector<int>> permuteUnique(vector<int>& nums) {path.clear();result.clear();vector<bool> used;used.resize(nums.size());sort(nums.begin(),nums.end());trackback(nums,used);return result;}
};感谢你耐心的看到这里ღ( ´･ᴗ･` )比心，如有哪里有错误请踢一脚作者o(╥﹏╥)o！
给个三连再走嘛~