代码随想录阅读笔记-回溯【全排列 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

思路 

本题和上一道题的区别在与给定一个可包含重复数字的序列，要返回所有不重复的全排列。

这里又涉及到去重了。

在组合总和以及子集问题中我们分别详细讲解了组合问题和子集问题如何去重。

那么排列问题其实也是一样的套路。

还要强调的是去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。

我以示例中的 [1,1,2]为例 （为了方便举例，已经排序）抽象为一棵树，去重过程如图：

47.全排列II1

图中我们对同一树层，前一位（也就是nums[i-1]）如果使用过，那么就进行去重。

一般来说：组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。

代码如下：

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    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] == true，说明同一树枝nums[i - 1]使用过
            // used[i - 1] == false，说明同一树层nums[i - 1]使用过
            // 如果同一树层nums[i - 1]使用过则直接跳过
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            if (used[i] == false) {
                used[i] = true;
                path.push_back(nums[i]);
                backtracking(nums, used);
                path.pop_back();
                used[i] = false;
            }
        }
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        result.clear();
        path.clear();
        sort(nums.begin(), nums.end()); // 排序
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};

// 时间复杂度: 最差情况所有元素都是唯一的。复杂度和全排列1都是 O(n! * n) 对于 n 个元素一共有 n! 中排列方案。而对于每一个答案，我们需要 O(n) 去复制最终放到 result 数组
// 空间复杂度: O(n) 回溯树的深度取决于我们有多少个元素
  • 时间复杂度: O(n! * n)
  • 空间复杂度: O(n)

拓展

大家发现，去重最为关键的代码为：

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

如果改成 used[i - 1] == true， 也是正确的!，去重代码如下：

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

这是为什么呢，就是上面我刚说的，如果要对树层中前一位去重，就用used[i - 1] == false，如果要对树枝前一位去重用used[i - 1] == true。

对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高！

这么说是不是有点抽象？

来来来，我就用输入: [1,1,1] 来举一个例子。

树层上去重(used[i - 1] == false)，的树形结构如下：

47.全排列II2

树枝上去重（used[i - 1] == true）的树型结构如下：

47.全排列II3

大家应该很清晰的看到，树层上对前一位去重非常彻底，效率很高，树枝上对前一位去重虽然最后可以得到答案，但是做了很多无用搜索。

接下来着重 复习并总结一下回溯法中需要去重的问题

在子集Ⅱ中的去重和 递增子序列中的去重 都是 同一父节点下本层的去重。

子集Ⅱ问题也可以使用set针对同一父节点本层去重，但子集问题一定要排序，为什么呢？

我用没有排序的集合{2,1,2,2}来举例子画一个图，如图：

90.子集II2

图中，大家就很明显的看到，子集重复了。那么下面我针对子集Ⅱ问题给出使用set来对本层去重的代码实现。

​​​​​​​子集Ⅱ问题

使用set去重的版本如下：

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIndex, vector<bool>& used) {
        result.push_back(path);
        unordered_set<int> uset; // 定义set对同一节点下的本层去重
        for (int i = startIndex; i < nums.size(); i++) {
            if (uset.find(nums[i]) != uset.end()) { // 如果发现出现过就pass
                continue;
            }
            uset.insert(nums[i]); // set跟新元素
            path.push_back(nums[i]);
            backtracking(nums, i + 1, used);
            path.pop_back();
        }
    }

public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        result.clear();
        path.clear();
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end()); // 去重需要排序
        backtracking(nums, 0, used);
        return result;
    }
};

再补充一些常见的错误写法，

错误写法一

把uset定义放到类成员位置，然后模拟回溯的样子 insert一次，erase一次。

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    unordered_set<int> uset; // 把uset定义放到类成员位置
    void backtracking(vector<int>& nums, int startIndex, vector<bool>& used) {
        result.push_back(path);

        for (int i = startIndex; i < nums.size(); i++) {
            if (uset.find(nums[i]) != uset.end()) {
                continue;
            }
            uset.insert(nums[i]);   // 递归之前insert
            path.push_back(nums[i]);
            backtracking(nums, i + 1, used);
            path.pop_back();
            uset.erase(nums[i]);    // 回溯再erase
        }
    }

在树形结构中，如果把unordered_set uset放在类成员的位置（相当于全局变量），就把树枝的情况都记录了，不是单纯的控制某一节点下的同一层了。

如图：

90.子集II1

可以看出一旦把unordered_set uset放在类成员位置，它控制的就是整棵树，包括树枝。

所以这么写不行！

错误写法二

有同学把 unordered_set uset; 放到类成员位置，然后每次进入单层的时候用uset.clear()。

代码如下：

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    unordered_set<int> uset; // 把uset定义放到类成员位置
    void backtracking(vector<int>& nums, int startIndex, vector<bool>& used) {
        result.push_back(path);
        uset.clear(); // 到每一层的时候，清空uset
        for (int i = startIndex; i < nums.size(); i++) {
            if (uset.find(nums[i]) != uset.end()) {
                continue;
            }
            uset.insert(nums[i]); // set记录元素
            path.push_back(nums[i]);
            backtracking(nums, i + 1, used);
            path.pop_back();
        }
    }

uset已经是全局变量，本层的uset记录了一个元素，然后进入下一层之后这个uset（和上一层是同一个uset）就被清空了，也就是说，层与层之间的uset是同一个，那么就会相互影响。

所以这么写依然不行！

组合问题和排列问题，其实也可以使用set来对同一节点下本层去重，下面我都分别给出实现代码。

组合总和 II

使用set去重的版本如下：

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum == target) {
            result.push_back(path);
            return;
        }
        unordered_set<int> uset; // 控制某一节点下的同一层元素不能重复
        for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
            if (uset.find(candidates[i]) != uset.end()) {
                continue;
            }
            uset.insert(candidates[i]); // 记录元素
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, sum, i + 1);
            sum -= candidates[i];
            path.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        path.clear();
        result.clear();
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, 0);
        return result;
    }
};

全排列 II

使用set去重的版本如下：

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking (vector<int>& nums, vector<bool>& used) {
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        unordered_set<int> uset; // 控制某一节点下的同一层元素不能重复
        for (int i = 0; i < nums.size(); i++) {
            if (uset.find(nums[i]) != uset.end()) {
                continue;
            }
            if (used[i] == false) {
                uset.insert(nums[i]); // 记录元素
                used[i] = true;
                path.push_back(nums[i]);
                backtracking(nums, used);
                path.pop_back();
                used[i] = false;
            }
        }
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        result.clear();
        path.clear();
        sort(nums.begin(), nums.end()); // 排序
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};

两种写法的性能分析

需要注意的是：使用set去重的版本相对于used数组的版本效率都要低很多，大家在leetcode上提交，能明显发现。

主要是因为程序运行的时候对unordered_set 频繁的insert，unordered_set需要做哈希映射（也就是把key通过hash function映射为唯一的哈希值）相对费时间，而且insert的时候其底层的符号表也要做相应的扩充，也是费时的。而使用used数组在时间复杂度上几乎没有额外负担！

使用set去重，不仅时间复杂度高了，空间复杂度也高了，组合，子集，排列问题的空间复杂度都是O(n)，但如果使用set去重，空间复杂度就变成了O(n^2)，因为每一层递归都有一个set集合，系统栈空间是n，每一个空间都有set集合。而used数组是全局变量，每层与每层之间公用一个used数组，所以空间复杂度是O(n + n)，最终空间复杂度还是O(n)。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/558073.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

JVM 性能调优命令（jps,jinfo,jstat,jstack,jmap)

JVM 性能调优命令（jps,jinfo,jstat,jstack,jmap)

常用命令&#xff1a;jps、jinfo、jstat、jstack、jmap jps jps查看java进程及相关信息 jps -l 输出jar包路径&#xff0c;类全名 jps -m 输出main参数 jps -v 输出JVM参数jps命令示例 显示本机的Java虚拟机进程&#xff1a; # jps 15729 jar 92153 Jps 90267 Jstat显示主类…
阅读更多...
c 多文件编程

c 多文件编程

1.结构目录 声明类:用于声明方法,方便方法管理和调用&#xff1b; 实现类:用于实现声明的方法; 应用层:调用方法使用 写过java代码的兄弟们可以这么理解&#xff1a; 声明类 为service层 实现类 为serviceimpl层 应用层 为conlloter层 2.Dome 把函数声明放在头文件xxx.h中&…
阅读更多...
外包干了7个月，技术退步明显。。。。。

外包干了7个月，技术退步明显。。。。。

先说一下自己的情况&#xff0c;本科生&#xff0c;19年通过校招进入广州某软件公司&#xff0c;干了接近4年的功能测试&#xff0c;今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了四年的功能测试…
阅读更多...
Spark01

Spark01

Spark01 一. Spark概述二. Spark环境部署 - Local三. Spark环境部署 - Standalone1. Standalone集群概述2. Standalone环境部署3. 测试环境 四. Spark环境部署 - Standalone-HA1. 安装部署Zookeeper1. 下载2. zookeeper安装3. 配置StandAlone-HA集群 五. Spark On YARN -- 重点…
阅读更多...
CSS 实现视差滚动效果

CSS 实现视差滚动效果

一、是什么 视差滚动&#xff08;Parallax Scrolling&#xff09;是指多层背景以不同的速度移动&#xff0c;形成立体的运动效果&#xff0c;带来非常出色的视觉体验 我们可以把网页解刨成&#xff1a;背景层、内容层、悬浮层 当滚动鼠标滑轮的时候&#xff0c;各个图层以不…
阅读更多...
Nuclei 减少漏报的使用小技巧

Nuclei 减少漏报的使用小技巧

在最近工作的渗透测试项目中发现Nuclei存在一个问题&#xff0c;就是相同的网站连续扫描多次会出现漏报的情况&#xff0c;此前没有注意过这个情况&#xff0c;所以写篇文章记录一下。 在此之前我的常用命令都是一把梭&#xff0c;有就有没有就继续其他测试 $ nuclei -u htt…
阅读更多...
锂电池寿命预测 | Matlab基于GRU门控循环单元的锂电池寿命预测

锂电池寿命预测 | Matlab基于GRU门控循环单元的锂电池寿命预测

目录 预测效果基本介绍程序设计参考资料 预测效果 基本介绍 锂电池寿命预测 | Matlab基于GRU门控循环单元的锂电池寿命预测 Matlab基于GRU的锂电池剩余寿命预测 基于GRU的锂电池剩余寿命预测&#xff08;单变量&#xff09; 运行环境Matlab2020及以上 锂电池的剩余寿命预测是…
阅读更多...
【简单介绍下K-means聚类算法】

【简单介绍下K-means聚类算法】

&#x1f308;个人主页: 程序员不想敲代码啊 &#x1f3c6;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f44d;点赞⭐评论⭐收藏 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共…
阅读更多...
​面试经典150题——从前序与中序遍历序列构造二叉树

​面试经典150题——从前序与中序遍历序列构造二叉树

​ 1. 题目描述 2. 题目分析与解析 二叉树的前序、中序和后序遍历 二叉树的前序、中序和后序遍历是树的三种基本遍历方式&#xff0c;它们是通过不同的顺序来访问树中的节点的。 前序遍历&#xff08;Pre-order traversal&#xff09;&#xff1a; 访问根节点 前序遍历左子树…
阅读更多...
Linux-Stunnel介绍

Linux-Stunnel介绍

1、定义 Stunnel是一个自由的跨平台软件&#xff0c;用于提供全局的TLS/SSL服务。针对本身无法进行TLS或SSL通信的客户端及服务器&#xff0c;Stunnel可提供安全的加密连接。该软件可在许多操作系统下运行&#xff0c;包括Unix-like系统&#xff0c;以及Windows。Stunnel依赖于…
阅读更多...
15、ESP32 BLE

15、ESP32 BLE

低功耗蓝牙&#xff1a; 低功耗蓝牙&#xff0c;简称 BLE&#xff0c;是蓝牙的省电版本。BLE 的主要应用是短距离传输少量数据&#xff08;低带宽&#xff09;。与经典蓝牙不同&#xff0c;BLE 始终保持睡眠模式&#xff0c;除非启动连接&#xff0c;这使得它消耗的功率非常低。…
阅读更多...
智能设备订购如何使药品供应链受益

智能设备订购如何使药品供应链受益

自从 Covid-19 大流行扰乱全球供应链以来&#xff0c;制药行业对增强弹性的需求变得比以往任何时候都更加重要。药品供应链已经开始数字化转型&#xff0c;采用新技术有助于确保药品和关键物资按时到达目的地并支持长期业务战略。其中一种解决方案是在移动设备上进行智能设备订…
阅读更多...
在 Ubuntu 12.10 安装 wxPython

在 Ubuntu 12.10 安装 wxPython

安装 wxPython 可以使用 pip 工具&#xff0c;但在 Ubuntu 12.10 上需要首先安装 wxPython 的依赖项。请注意&#xff0c;Ubuntu 12.10 已于2013年终止支持&#xff0c;建议升级到更高版本的 Ubuntu。以下是在 Ubuntu 12.10 上安装 wxPython 的一般步骤&#xff1a; 一、问题背…
阅读更多...
HTML学习笔记：（二）框架实例

HTML学习笔记：（二）框架实例

2、 框架实例 注意&#xff1a;frameset不能和body标签共存 <frameset>元素是用于创建框架页面的&#xff0c;它允许在一个浏览器窗口中显示多个HTML页面。然而&#xff0c;<frameset>是一种较旧的方式来构建网页&#xff0c;它不符合现代Web标准&#xff08;比如…
阅读更多...
【VTKExamples::Meshes】第 十四期 ExtractEdges

【VTKExamples::Meshes】第 十四期 ExtractEdges

很高兴在雪易的CSDN遇见你 VTK技术爱好者 QQ：870202403 公众号：VTK忠粉 前言 本文分享VTK样例ExtractEdges，并解析接口vtkExtractEdges，希望对各位小伙伴有所帮助！ 感谢各位小伙伴的点赞+关注，小易会继续努力分享，一起进步！ 你的点赞就是我的动力(＾Ｕ＾)ノ~…
阅读更多...
深入理解JAVA垃圾收集器CMS,G1工作流程原理 GC流程图 什么社会触发Minor GC？触发MinorGC过程。Full GC 过程。

深入理解JAVA垃圾收集器CMS,G1工作流程原理 GC流程图 什么社会触发Minor GC？触发MinorGC过程。Full GC 过程。

java CMS&#xff0c;G1垃圾收集器工作流程原理浅析 JVM内存空间基础知识点&#xff08;基于JDk1.8&#xff09; 1.方法区&#xff1a;逻辑概念&#xff0c;元空间&#xff0c;方法区主要用于存储类的信息、常量池、方法数据、方法代码等。方法区逻辑上属于堆的一部分&#xf…
阅读更多...
Github 2024-04-15 开源项目日报Top10

Github 2024-04-15 开源项目日报Top10

根据Github Trendings的统计，今日(2024-04-15统计)共有10个项目上榜。根据开发语言中项目的数量，汇总情况如下： 开发语言项目数量Python项目4TypeScript项目2HTML项目1JavaScript项目1C++项目1Rust项目1Mojo项目1Fooocus: 图像生成软件 创建周期：188 天开发语言：Python协议…
阅读更多...
Mathtype用法记录

Mathtype用法记录

常用写法 公式编号 给公式插入编号的方法 手动修改公式编号为指定值 例如编号(8.3.1)修改为(8.3.7)&#xff0c;即章、节号不变&#xff0c;公式序号改为7。 可修改编号的域代码&#xff0c;比如(8.3.1)的域代码为&#xff1a; { { MACROBUTTON MTPlaceRef \* MERGEFORMAT…
阅读更多...
【星瑞格】SinoDB国产数据库安装初体验及学习指南

【星瑞格】SinoDB国产数据库安装初体验及学习指南

今天和大家一起来看看一款来自福建的国产数据库——SinoDB。本人很早就听说过这款数据库&#xff0c;而且星瑞格公司就在同一栋办公楼。虽然以前就已经对这颗国产数据库有一定的了解&#xff0c;并没有真正的去使用一把。随着数据库国产化改造工作的推进&#xff0c;身边的客户…
阅读更多...
使用docker配置CCM-SLAM

使用docker配置CCM-SLAM

一.Docker环境配置 1.拉取Docker镜像 sudo docker pull ubuntu:18.04拉取的为ununtu18版本镜像&#xff0c;环境十分干净&#xff0c;可以通过以下命令查看容器列表 sudo docker images 如果想删除多余的docker image&#xff0c;可以使用指令 sudo docker rmi -f <id&g…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站