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]]

实现代码与解析：

回溯：

class Solution {
public:vector<int> path;//记录路径vector<vector<int>> result;//记录结果void backtracking(vector<int> nums,vector<int> used){//全部遍历完了if(path.size()==nums.size()){result.push_back(path);return;}for(int i=0;i<nums.size();i++){//跳过已经使用过的if(used[i]==1) continue;used[i]=1;path.push_back(nums[i]);//处理backtracking(nums,used);//递归path.pop_back();//回溯used[i]=0;//回溯}}vector<vector<int>> permute(vector<int>& nums) {vector<int> used(nums.size(),0);//初始化为0backtracking(nums,used);return result;}
};

原理思路：

此题寻找的是全排列组合，所以我们每次遍历都要重头开始寻找，而不是向后去循环，所以显然不能重复去循环一个数，所以我们用一个used数组去记录已经用过的数，再次遇到时就跳过此次循环即可。

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]]

实现代码与解析：

回溯：

class Solution {
public:vector<int> path;//记录路径vector<vector<int>> result;//记录结果void backtracking(vector<int> nums,vector<int> used){//全部遍历完了if(path.size()==nums.size()){result.push_back(path);return;}for(int i=0;i<nums.size();i++){//数层上去重if(i>0&&nums[i]==nums[i-1]&&used[i-1]==0) continue;//树枝上跳过已经用过的数if(used[i]==1) continue;used[i]=1;path.push_back(nums[i]);//处理backtracking(nums,used);//递归path.pop_back();//回溯used[i]=0;//回溯}}vector<vector<int>> permuteUnique(vector<int>& nums) {vector<int> used(nums.size(),0);sort(nums.begin(),nums.end());backtracking(nums,used);return result;}
};

原理思路：

在上一题的基础上，仅仅多了一个树层去重的逻辑，当然这样写要先排序。

//数层上去重
if(i>0&&nums[i]==nums[i-1]&&used[i-1]==0) continue;

其实最重要的就是理解为什么要加上used[i-1]=0，因为我们这里是树层上的去重，确保的是当前层循环不出现同样的数，而在不同层上是可以出现同样的数，若与此次循环相同的上一个数是在上一层循环就用过的数，那么此层循环就可以取这个数，所以要加上这个逻辑。为什么以往的题就不用加呢，因为以往的题递归都是从i+1的逻辑开始遍历，本身就避免了这种情况，大家可以仔细想一想。