网站建设补充报价单,网站建设 技术指标,论述制作网站的一般过程,网站开发制作熊掌号力扣日记#xff1a;【回溯算法篇】47. 全排列 II 日期#xff1a;2023.2.22 参考#xff1a;代码随想录、力扣 47. 全排列 II
题目描述 难度#xff1a;中等 给定一个可包含重复数字的序列 nums #xff0c;按任意顺序 返回所有不重复的全排列。
示例 1#xff1a; 输…力扣日记【回溯算法篇】47. 全排列 II 日期2023.2.22 参考代码随想录、力扣 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]] 提示
1 nums.length 8-10 nums[i] 10
题解
cppver
class Solution {
public:
#define SOLUTION 2vectorint path;vectorvectorint result;vectorvectorint permuteUnique(vectorint nums) {// 排序sort(nums.begin(), nums.end());vectorbool used(nums.size(), false);backtracking(nums, used);return result;}
#if SOLUTION 1void backtracking(vectorint nums, vectorbool used) { // 因为存在重复值所以不宜用哈希表记录是否使用过// 终止条件if (path.size() nums.size()) {result.push_back(path);return;}int lastNum -11;// for 横向遍历for (int i 0; i nums.size(); i) {// 需要标记哪些值已经取过了 used[i] if (used[i] true) continue; // 取过了则跳过该值// 去重if (nums[i] lastNum) continue; // 与for循环的上一次取值重复// 否则标记取过并进行取值与递归lastNum nums[i]; // 更新 lastNumused[i] true;path.push_back(nums[i]);backtracking(nums, used);path.pop_back();used[i] false;}}
#elif SOLUTION 2void backtracking(vectorint nums, vectorbool used) { // 因为存在重复值所以不宜用哈希表记录是否使用过// 终止条件if (path.size() nums.size()) {result.push_back(path);return;}// 使用 nums[i] nums[i-1] 结合 used[i-1] 来判断是树枝重复还是树层重复// 树层重复的条件为i 0 nums[i] nums[i-1] used[i-1] false 上一个位置的元素未使用说明是树层// 树枝重复的条件为i 0 nums[i] nums[i-1] used[i-1] true// for 横向遍历for (int i 0; i nums.size(); i) {// 树枝纵向递归标记哪些值已经取过了 used[i] if (used[i] true) continue; // 取过了则跳过该值// 树层用于去重if (i 0 nums[i] nums[i-1] used[i-1] false) continue; // 与for循环的上一次取值重复// 否则标记取过并进行取值与递归used[i] true;path.push_back(nums[i]);backtracking(nums, used);path.pop_back();used[i] false;}}
#endif
};复杂度
时间复杂度: O(n! * n)空间复杂度: O(n)
思路总结
本题与 46. 全排列 的区别在于集合中可能存在重复元素。因此需要考虑去重即在46题的基础上需要在for循环遍历横向遍历中过滤掉相同的元素但又不能影响到纵向递归时元素的可重复选取。不同于 40.组合总和 II 和 90.子集 II全排列在for循环遍历时不能使用startindex即每次for循环遍历都会从头开始遍历不能直接在for循环中用 if (i 0 nums[i] nums[i-1]) continue; 来跳过重复元素因为这样会使得在纵向递归时也无法选取到重复元素。因此需要一个只会影响到横向遍历的变量即代码中在for循环前定义的lastNum这样每次for循环前会重置lastNum用来记录相同层中for循环上次取到的元素——如果当前值与for循环上次取到的值相同则跳过当前元素。且只有在该值也满足“纵向递归中当前位置未取过”的条件used[i] false才会更新该lastNum即当前值能进行取值、递归才会更新。注意 去重 要提前做好排序。由于本题存在重复元素所以不能使用按值大小记录是否取过的哈希表作为used而要使用按位置记录的usedvectorbool used(nums.size(), false)。去重与是否使用过的if-continue判断条件的前后位置不影响也可以写在一起但取值、更新、递归、回溯等所谓处理节点一定要放在两者后面。 树形结构示意图 代码随想录版本 使用 nums[i] nums[i-1] 结合 used[i-1] 来判断是树枝重复还是树层重复 树层重复的条件为i 0 nums[i] nums[i-1] used[i-1] false 上一个位置的元素未使用说明是树层树枝重复的条件为i 0 nums[i] nums[i-1] used[i-1] true如图 所以在for循环中 第一个条件用于排列取值// 树枝纵向递归标记哪些值已经取过了 used[i]
if (used[i] true) continue; // 取过了则跳过该值第二个条件用于树枝去重if (i 0 nums[i] nums[i-1] used[i-1] false) continue;
