全排列
给定一个不含重复数字的数组 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 来确定下一层递归的开头, 那么我们该用什么来确定开头呢?
NO! NO!, 排列的开头就是 0, 用used数组来确定是否选取该数字
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; } };
