第四章

  • 全排列
    • 题目理解
    • 步骤
      • 树形图
      • 递归函数
      • 递归结束条件
      • 单层逻辑
    • 代码
  • 全排列II
    • 题目理解
    • 步骤
      • 递归函数
      • 递归结束条件
      • 单层逻辑
    • 代码

全排列

力扣链接

给定一个不含重复数字的数组 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 中的所有整数 互不相同

题目理解

很明显这是用回溯算法来写的
相比较之前写的 组合 :

  • startindex — — 下一层递归的开头, 即确定下一次递归的区间, 确保不会重复

元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1，所以处理排列问题就不用使用startIndex了

那我们这里的排列, 每次剩下的区间不是上一个区间的下一个— — startindex就失去了意义

那么我们这次需要一个数组来记录每个数的使用情况 — — used数组

步骤

树形图

递归函数

首先, 还是两个全局数组

vector<int> path;vector<vector<int>> result;

递归函数的返回 还是 void, 没有startindex, 但是要用 used数组来记录每个数的使用情况

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

递归结束条件

我们发现是在叶子节点接收结果, 那么就是

if(path.size() == nums.size()){result.push_back(path);return ; // 由于是叶子节点收结果, 直接返回}

单层逻辑

如果我们不使用 startindex 来确定下一层递归的开头, 那么我们该用什么来确定开头呢” />for(int i = 0; i < nums.size(); i++){// 该数字被使用过, 就跳过if(used[i] == false)continue;used[i] = true; // 使用, 那就先把它记录一下path.push_back(nums[i]); // 处理节点backtracking(nums, used); // 下一层(纵向)used[i] = false; // 回溯}

代码

class Solution {public:vector<int> path;vector<vector<int>> result;void backtracking(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(used[i] == true)continue;used[i] = true;path.push_back(nums[i]);backtracking(nums, used);path.pop_back();used[i] = false;}}vector<vector<int>> permute(vector<int>& nums) {vector<bool> used(nums.size(), false);backtracking(nums, used);return result;}};

全排列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

题目理解

跟上面的题目很相似, 但是 有重复的数字 && 返回不重复的全排列
⇒ 意味着我们要 去重
组合中的去重 — — 排序 + 用used来记录每个数字的使用情况
其实在 排列中的去重, 也是同样的思路

️为什么要排序” /> 通过排序, 使我们通过相邻的位置来判断是否使用过

不难发现:

  • 当 nums[i] == nums[i – 1]时, used[i – 1] = false — — 树层去重
  • 当 nums[i] == nums[i – 1]时, used[i – 1] = true — — 树枝去重

步骤

递归函数

首先, 还是两个全局数组

vector<int> path;vector<vector<int>> result;

递归函数的返回 还是 void, 没有startindex, 但是要用 used数组来记录每个数的使用情况

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

递归结束条件

我们发现是在叶子节点接收结果, 那么就是

if(path.size() == nums.size()){result.push_back(path);return ; // 由于是叶子节点收结果, 直接返回}

单层逻辑

 for(int i = 0; i < nums.size(); i++) {// used[i - 1 ] == false是树层去重, used[i - 1 ] == true是树枝去重 if(i > 0 && nums[i - 1] == nums[i] && used[i - 1] == false)continue;// 这里跟 组合 那里的不一样, 由于组合有startindex, 知道从剩下集合的开头// 而排序, 每次都是从 0 开始, 用used数组来记录使用情况, // 那么肯定要判断一下我们当前数的使用情况if(used[i] == true)continue;used[i] = true; // 记录一下path.push_back(nums[i]); // 记录节点backtracking(nums, used); // 下一层递归// 回溯path.pop_back(); used[i] = false; }}

代码

class Solution {public:vector<int> path;vector<vector<int>> result;void backtracking(vector<int>& nums, vector<bool>& used){if(path.size() == nums.size()){result.push_back(path);return ;} for(int i = 0; i < nums.size(); i++) {// used[i - 1 ] == false是树层去重, used[i - 1 ] == true是树枝去重 if(i > 0 && nums[i - 1] == nums[i] && used[i - 1] == false)continue;// 这里跟 组合 那里的不一样, 由于组合有startindex, 知道从剩下集合的开头// 而排序, 每次都是从 0 开始, 用used数组来记录使用情况, // 那么肯定要判断一下我们当前数的使用情况if(used[i] == true)continue;used[i] = true; // 记录一下path.push_back(nums[i]); // 记录节点backtracking(nums, used); // 下一层递归// 回溯path.pop_back(); used[i] = false; }}vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end()); // 一定记得要排序vector<bool> used(nums.size(), false); // 都先初始化为false -- -- 没用过backtracking(nums, used);return result;}};

天地转，光阴迫，一万年太久，只争朝夕。一一毛泽东