代码随想录 | 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.函数参数和返回值

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

res存放结果

path存放目前放入的数

nums题目数组

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

2.终止条件

由全排列性质易知。

1
2
3
4
5
if(path.size()==nums.size())
{
	res.push_back(path);
    return;
}

3.本层代码逻辑

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

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

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

1
2
3
4
5
6
7
8
9
10
11
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;
          }
      }

完整代码：

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
30
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都写过，这里不再赘述

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

完整代码：

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
30
31
32
33
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;
    }
};