代码随想录 | Day32 | 回溯算法：排列问题

代码随想录 | Day32 | 回溯算法：排列问题

主要学习内容：

1.复习树枝去重

2.复习树层去重

46.全排列

46. 全排列 - 力扣（LeetCode）

解法思路：

首先通过前面的学习，我们知道，每层递归函数的for循环是用来形成树形结构这一层的所有结点（比如main里面的递归函数的for循环形成了树形结构的第二层，剩下的结点都是递归得来的）

这道题的全排列，和组合问题最大的区别就是

1.[1,2,3]和[1,3,2]不是一个东西

2.因为[2,1,3]这种结果的存在，使得选了2以后要继续选1，说明每层递归函数的for循环的i都要从0开始而不是index，并且由于选了2了不能重复选择，在下面的函数里面碰到了2要跳过

由此可见，我们还需要一个used来记录我们已经选过的值（这就是树枝去重）

1.函数参数和返回值

vector<vector<int>> res;
void backtracking(vector<int>& nums,vector<int> path,vector<bool> used)

res存放结果

path存放目前放入的数

nums题目数组

used标记我们已经放过的数避免重复

2.终止条件

由全排列性质易知。

if(path.size()==nums.size())
{res.push_back(path);return;
}

3.本层代码逻辑

因为是全排列，每层递归函数的for循环都要把整个数组遍历一遍

used初始化全为false，选过的置为true

每当遇到false才会进入下层，将nums[i]压入path，used[i]置为true，遇到true直接跳过本次循环

		for(int i=0;i<nums.size();i++){if(used[i]==false){path.push_back(nums[i]);used[i]=true;backtracking(nums,path,used);path.pop_back();used[i]=false;}}

完整代码：

class Solution {
public:vector<vector<int>> res;void backtracking(vector<int>& nums,vector<int> path,vector<bool> used){if(path.size()==nums.size()){res.push_back(path);return ;}for(int i=0;i<nums.size();i++){if(used[i]==false){path.push_back(nums[i]);used[i]=true;backtracking(nums,path,used);path.pop_back();used[i]=false;}}}vector<vector<int>> permute(vector<int>& nums) {vector<int> path;vector<bool> used(nums.size(),false);backtracking(nums,path,used);return res;}
};

47.全排列II

47. 全排列 II - 力扣（LeetCode）

思路：

这题是说明在树层之间不能有重复的，

比如[1,1,2]，树形结构中的第二层（选择有1,1,2）直接把第二个1的分支给砍掉

那么就只需在上一题的基础上加上树层去重即可。

在40.组合总和和90子集II都写过，这里不再赘述

if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false)continue;

完整代码：

class Solution {
public:vector<vector<int>> res;void backtracking(vector<int>& nums,vector<int> path,vector<bool> used){if(path.size()==nums.size()){res.push_back(path);return ;}for(int i=0;i<nums.size();i++){if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false)continue;if(used[i]==false){path.push_back(nums[i]);used[i]=true;backtracking(nums,path,used);path.pop_back();used[i]=false;}}}vector<vector<int>> permuteUnique(vector<int>& nums) {vector<int> path;vector<bool> used(nums.size(),false);sort(nums.begin(),nums.end());backtracking(nums,path,used);return res;}
};