当前位置：首页 > news >正文

解决LeetCode 47. 全排列 II 问题的正确姿势：深入分析剪枝与状态跟踪

news 来源：原创 2025/6/17 5:14:29

文章目录

- 问题描述
- 常见错误代码与问题分析
- - 错误代码示例
  - 错误分析
- 正确解决方案
- - 修正后的代码
  - 关键修正点
- 核心逻辑详解
- - 1. 为何使用 `boolean[] used` 而非 `HashSet`？
  - 2. 剪枝条件 `!used[i - 1]` 的作用
- 场景对比：何时用数组？何时用哈希表？
- 实例分析
- 总结

问题描述

给定一个可能包含重复元素的整数数组 nums，返回所有可能的唯一全排列。例如，输入 nums = [1,1,2]，期望输出为：
[[1,1,2], [1,2,1], [2,1,1]]。

常见错误代码与问题分析

错误代码示例

class Solution {public List<List<Integer>> permuteUnique(int[] nums) {List<List<Integer>> result = new ArrayList<>();Arrays.sort(nums);backTrack(result, new ArrayList<>(), nums);return result;}public void backTrack(List<List<Integer>> result, List<Integer> path, int[] nums) {if (path.size() == nums.length) {result.add(new ArrayList(path));return;}HashSet<Integer> used = new HashSet<>();for (int i = 0; i < nums.length; i++) {if (i > 0 && nums[i] == nums[i - 1] || used.contains(nums[i])) {continue;}path.add(nums[i]);used.add(nums[i]);backTrack(result, path, nums);path.remove(path.size() - 1);}}
}

错误分析

错误使用 HashSet 跟踪元素
HashSet 仅通过值去重，无法区分相同值的不同索引。例如，在 nums = [1,1,2] 中，两个 1 会被视为重复，导致合法排列 [1,1,2] 被错误跳过。
剪枝条件不完整
原代码的剪枝条件 i > 0 && nums[i] == nums[i - 1] 未考虑元素的使用状态，无法正确避免同一层递归中的重复分支。

正确解决方案

修正后的代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;class Solution {public List<List<Integer>> permuteUnique(int[] nums) {List<List<Integer>> result = new ArrayList<>();if (nums == null || nums.length == 0) return result;Arrays.sort(nums);backtrack(result, new ArrayList<>(), nums, new boolean[nums.length]);return result;}private void backtrack(List<List<Integer>> result, List<Integer> path, int[] nums, boolean[] used) {if (path.size() == nums.length) {result.add(new ArrayList<>(path));return;}for (int i = 0; i < nums.length; i++) {if (used[i]) continue;if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;used[i] = true;path.add(nums[i]);backtrack(result, path, nums, used);path.remove(path.size() - 1);used[i] = false;}}
}

关键修正点

引入 boolean[] used 数组
通过索引精确记录元素是否被使用，区分相同值的不同位置。
完善剪枝条件
使用 i > 0 && nums[i] == nums[i - 1] && !used[i - 1] 确保仅在相同值的元素未被使用时剪枝，避免重复分支。

核心逻辑详解

1. 为何使用 `boolean[] used` 而非 `HashSet`？

区分相同值的不同索引
例如 nums = [1,1,2]，通过 used 数组可明确标记第一个 1（索引0）和第二个 1（索引1）的使用状态。
时间复杂度与空间效率
数组的索引访问为 O(1)，且内存连续，无哈希表动态扩容的开销。

2. 剪枝条件 `!used[i - 1]` 的作用

避免同一层递归的重复分支
当 nums[i] == nums[i-1] 且前一个元素未被使用时（!used[i-1]），说明已存在以该值开头的分支，需跳过当前元素。
允许深层递归使用相同值
若前一个元素已被使用（used[i-1] = true），则当前处于深层递归，允许生成 [1,1,2] 等合法排列。

场景对比：何时用数组？何时用哈希表？

场景	数组（boolean[]）	哈希表（HashSet）
是否需要区分相同值的不同位置	✔️（如全排列问题）	❌（仅判断值是否存在）
数据范围	小且连续（如 `n ≤ 1e6`）	大或不连续
时间复杂度	O(1)（直接索引访问）	O(1)（平均情况）
空间复杂度	固定空间	动态扩展
适用问题类型	排列、组合、子集（含重复元素）	去重、存在性判断（如两数之和）

实例分析

以 nums = [1,1,2] 为例：

排序后数组：[1,1,2]。
第一层递归：选择第一个 1（索引0），标记 used[0] = true。
第二层递归：允许选择第二个 1（索引1），标记 used[1] = true。
第三层递归：选择 2，生成排列 [1,1,2]。
回溯后剪枝：若尝试在第一层选择第二个 1，触发 !used[0] 剪枝条件，避免重复。

总结

优先使用数组：当需要区分相同值的不同位置或数据范围较小时。
灵活选择哈希表：当仅需判断值的存在性且数据稀疏时。
剪枝条件是处理重复元素的关键，需结合元素值和索引状态综合判断。

通过合理选择数据结构和剪枝策略，可高效解决全排列 II 及其他回溯问题。

解决LeetCode 47. 全排列 II 问题的正确姿势：深入分析剪枝与状态跟踪

文章目录问题描述常见错误代码与问题分析错误代码示例错误分析正确解决方案修正后的代码关键修正点核心逻辑详解1. 为何使用 boolean[] used 而非 HashSet？2. 剪枝条件 !used[i - 1] 的作用场景对比：何时用数组？何时用哈希表？…...

编程日记 2025/5/28 4:31:33

面向SDV的在环测试深度解析——仿真中间件SIL KIT应用篇

1.引言在汽车行业向软件定义汽车（SDV）转型的过程中，传统硬件在环（HIL）测试方案因难以适应新的技术架构与需求，其局限性日益凸显。传统HIL对硬件依赖性强，扩展性差，更换ECU或传感器…...

编程日记 2025/5/26 7:25:26

03算法学习_977、有序数组的平方

03算法学习_977、有序数组的平方 03算法学习_977、有序数组的平方题目描述：个人代码：学习思路：移除元素第一种写法：暴力解法题解关键点： 移除元素第二种写法：双指针法（快慢指针）题解…...

编程日记 2025/5/31 8:57:07

AWS Elastic Beanstalk控制台部署Spring极简工程(LB版)

问题之前文章《AWS Elastic Beanstalk控制台部署Spring极简工程》，是最简单的eb设置，里面没有负载均衡器的配置，这次，我需要尝试创建一个有LB的eb部署。步骤配置eb 打开eb网页开始创建应用程序，如下图&#xff…...

编程日记 2025/5/29 9:25:37

前端JSON序列化中的隐形杀手：精度丢失全解析与实战解决方案

当你在电商平台看到订单ID从 “1298035313029456899” 变成 “1298035313029456900”，或者在金融系统中发现账户余额 100.01 元变成了 100.00999999999999 元时，这很可能遭遇了前端开发中最隐蔽的陷阱之一 —— JSON序列化精度丢失。本文将深入解析这一问…...

编程日记 2025/5/25 13:28:25

防篡改小工具监测被该文件

核心功能模块哈希计算模块：通过 SHA-256 算法计算文件的哈希值，用于唯一标识文件内容。基线构建模块：遍历指定目录下的所有文件，计算哈希值并保存到 JSON 文件中，形成初始基线。文件监控模块：使用 watchd…...

编程日记 2025/5/21 11:11:22

【四川省专升本计算机基础】第二章计算机软硬件基础（1）

【四川省专升本计算机基础】第二章计算机软硬件基础（1） 2.1 计算机系统组成计算机系统分为硬件系统和软件系统，其详细分类如下图所示：计算机硬件是由电子、机械和光电原件组成的各种设备和部件的总称。是计算机运行的物质基础。计算机软件是运行的各种程序、文档和…...

编程日记 2025/5/25 10:47:09

质量管理工程师面试总结

今天闲着无聊参加了学校招聘会的一家双选会企业，以下是面试的过程。此次面试采用的是一对多的形式。（此次三个求职者，一个面试官） 面试官：开始你们每个人先做个自我介绍吧。哈哈哈哈哈哈哈哈，其实我们…...

编程日记 2025/5/29 0:38:03

【沉浸式求职学习day41】【Servlet】

沉浸式求职学习 Servlet1.Servlet简介2.HelloServletServlet原理 3.ServletContext共享数据拿到初始化信息请求转发读取资源文件 Servlet 1.Servlet简介 Servlet就是sun公司开发动态web的一门技术。 Sun在这些API中提供一个接口叫做：Servlet，如果你想开…...

编程日记 2025/5/29 11:16:23

Java 多线程基础：Thread 类核心用法详解

一、线程创建 1. 继承 Thread 类（传统写法） class MyThread extends Thread { Override public void run() { System.out.println("线程执行"); } } // 使用示例 MyThread t new MyThread(); t.start(); 缺点：Java 单…...

编程日记 2025/5/27 4:51:58

时频分析的应用—外部信号的显影和定点清除

上面的图样是一张时频图，横坐标是时间，纵坐标是频率，颜色标志着主要的干扰源。50Hz工频谐波。这类信号在数据分析领域往往是需要过滤掉的杂波。因为这类信号足够强，所以他会在频域弥漫为一组同样特征的谐波信号，比如…...

编程日记 2025/5/24 12:02:56

目标检测指标计算

mAP（mean Average Precision） 概述预备参数：类别数，IoU阈值；根据模型输出的置信度分数，将所有预测框按从高到低排序；根据IoU是否超过阈值，判断每个预测框是 T P I o U TP_{IoU} T…...

编程日记 2025/5/29 22:26:53

独立开发者利用AI工具快速制作产品MVP

在当今快速发展的科技时代，独立开发者面临着前所未有的机遇与挑战。曾经需要花费数天甚至数周才能完成的产品MVP（Minimum Viable Product，最小可行性产品），如今借助强大的AI工具，可以在短短1小时内实现。 …...

编程日记 2025/6/1 12:37:22

YOLOv3深度解析：多尺度特征融合与实时检测的里程碑

一、YOLOv3的诞生：继承与突破的起点 YOLOv3作为YOLO系列的第三代算法，于2018年由Joseph Redmon等人提出。它在YOLOv2的基础上，针对小目标检测精度低、多类别标签预测受限等问题进行了系统性改进。通过引入多尺度特征图检测、残差网络架构和独…...

编程日记 2025/6/3 20:11:16

MATLAB中的概率分布生成：从理论到实践

MATLAB中的概率分布生成：从理论到实践引言 MATLAB作为一款强大的科学计算软件，在统计分析、数据模拟和概率建模方面提供了丰富的功能。本文将介绍如何使用MATLAB生成各种常见的概率分布，包括均匀分布、正态分布、泊松分布等，并…...

编程日记 2025/5/29 13:28:59

今日积累：若依框架配置QQ邮箱，来发邮件，注册账号使用

QQ邮箱SMTP服务器设置首先，我们需要了解QQ邮箱的SMTP服务器地址。对于QQ邮箱，SMTP服务器地址通常是smtp.qq.com。这个地址适用于所有使用QQ邮箱发送邮件的客户端。 QQ邮箱SMTP端口设置 QQ邮箱提供了两种加密方式：SSL和STARTTLS。根据您选…...

编程日记 2025/5/26 5:57:16

MySQL高效开发规范

1.基础规范 数据库字符集默认使用utf8mb4，兼容utf8，并支持存储emoji表情等四字节内容 禁止在线上生产环境做数据库压力测试 禁止从测试、开发环境、本机直连线上生产数据库 禁止在数据库中存储明文密码 禁止在数据库中存储图片、文件等大数据 …...

编程日记 2025/5/24 13:53:33

MySQL基础面试通关秘籍（附高频考点解析）

文章目录一、事务篇（必考重点）1.1 事务四大特性（ACID）1.2 事务实战技巧二、索引优化大法2.1 索引类型全家福2.2 EXPLAIN命令实战三、存储引擎选型指南3.1 InnoDB vs MyISAM 终极对决四、SQL优化实战手册4.1 慢查询七宗罪4.2 分…...

编程日记 2025/5/31 10:55:36

信贷风控笔记5——风控贷中策略笔记（面试准备13）

1.划分贷前贷中的标准：授信通过 2.框架：贷中风险管理：用信审批/贷中风险预警存量客户运营：不仅考虑风险，还要考虑客户需求、体验等因素，通过精细化的客户分层和差异化的权益调整方式&#xff…...

编程日记 2025/5/29 9:53:10

第五章：Linux用户管理

Linux系统中超级用户是root，通过超级用户root可以创建其它的普通用户，Linux是一个支持多用户的操作系统。在实际使用中，一般会分配给开发人员专属的账户，这个账户只拥有部分权限，如果权限太高，操作的范围过…...

编程日记 2025/5/21 21:01:46

低空态势感知：基于AI的DAA技术是低空飞行的重要安全保障-机载端地面端

低空态势感知：基于AI的DAA技术是低空飞行的重要安全保障-机载端&地面端目前空中已经有大量无人机和其他飞机，未来几年还会有空中出租车。目前，美国每年平均发生 15 到 25 起空中相撞事故。检测和避免 (DAA) 检测和避免 (DAA) 技术可…...

编程日记 2025/5/22 23:48:32

Web服务器怎么压测？可用什么软件？

针对Web服务器的压力测试，需要系统性地模拟真实用户请求，评估服务器在高并发场景下的性能表现（如吞吐量、响应时间、错误率等）。以下是完整的压测方案和工具选型指南：一、压测核心指标指标类型关键指标健康阈值参考并发能力最大支持并发用户数（Concurrency）错误率<…...

编程日记 2025/5/29 11:30:01

IntelliJ IDEA克隆项目失败的解决方法

IntelliJ IDEA克隆项目失败。咨询AI后，在它建议下，在Windows PowerShell中执行语句，成功克隆。操作流程如下； 1. 检查网络连接确保你的网络连接稳定，尝试更换网络环境或使用有线连接代替无线连接。 2. 删除项目 …...

编程日记 2025/5/20 10:36:20

云存储最佳实践

大家好,我是Petter Guo 对Coding充满热情的🐂🐎，坚信实操出真知。在这里，你将听到最真实的经验分享，绝不贩卖焦虑，只提供积极向上的硬核干货，助你一路前行！ 如果对你有帮助, 请点赞…...

编程日记 2025/5/27 23:52:26

矫平机技术新维度：材料科学、数字孪生与零缺陷制造

矫平机技术正经历从"被动修正"到"主动预判"的范式革命。本文聚焦三大前沿方向，揭示如何通过跨学科融合实现金属板材加工的极限突破。一、微观组织调控：材料科学与矫平工艺的量子纠缠晶粒定向技术通过矫平过程中的应变诱导取向&a…...

编程日记 2025/5/30 10:43:09

Dify中使用插件LocalAI配置模型供应商报错

服务器使用vllm运行大模型，今天在Dify中使用插件LocalAI配置模型供应商后，使用工作流的时候，报错：“Run failed: PluginInvokeError: {"args":{},"error_type":"ValueError","message":&…...

编程日记 2025/5/29 17:57:12

第二天的尝试

目录一、每日一言二、练习题三、效果展示四、下次题目五、总结一、每日一言清晰的明白自己想要的是什么，培养兴趣也好，一定要有自己的一技之长。我们不说多优秀，但是如果父母需要我们出力，不要只有眼泪。二、练习题对…...

编程日记 2025/5/27 5:28:51

专业版降重指南：如何用Python批量替换同义词？自动化操作不香嘛？

还在手动一个个改词降重？👀 是兄弟就别再CtrlF了，来试试Python自动同义词替换批量降重法，简直是论文改写效率神器！ 这篇我们来一波实操干货： 👉 如何用Python写出一个自动替换论文关键词的脚本…...

编程日记 2025/6/1 18:06:44

动态图标切换的艺术

动态图标切换的艺术 - Vue实战指南图标切换的本质：状态与视觉的双重舞蹈在前端开发中，图标切换就像我们日常生活中的换装游戏。想象一下，当你按下卧室的开关，灯泡从暗变亮；当你打开衣柜，选择不同场合的着装。图标切换的核心就是根据状态变化呈现不同的视觉效果。方…...

编程日记 2025/5/20 10:32:52

最小二乘法：从房价预测到损失计算

以下通过一个简单例子说明 y = w x + b y = wx + b y=...

编程日记 2025/5/29 17:28:22

C++ asio网络编程(7)增加发送队列实现全双工通信

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档文章目录前言一、数据节点设计二、封装发送接口介绍锁mutex和加锁工具lock_guard回调函数的实现为什么在回调函数中也要加锁修改读回调总结前言前文介绍了通过智能指针实…...

编程日记 2025/6/3 8:39:44

【C语言字符函数和字符串函数(一)】--字符分类函数，字符转换函数，strlen，strcpy，strcat函数的使用和模拟实现

目录一.字符分类函数 1.1--字符分类函数的理解 1.2--字符分类函数的使用二.字符转换函数 2.1--字符转换函数的理解 2.2--字符转换函数的使用三.strlen的使用和模拟实现 3.1--strlen的使用演示 3.2--strlen的返回值 3.3--strlen的模拟实现四.strcpy的使用和模拟实现…...

编程日记 2025/5/31 8:51:33

ADC深入——SNR、SFDR、ENOB等概念

目录 SNR（Spurious‑Free Dynamic Range 信噪比） ENOB（Effective Number Of Bits 有效位） SFDR（Spurious‑Free Dynamic Range） 感觉SNR和SFDR差不多？看看下图输入带宽混叠带通采样/欠…...

编程日记 2025/5/26 7:30:00

逻辑回归（二分类）

一.逻辑回归的由来逻辑回归不是一个回归的算法，不是用来做预测的，逻辑回归是一个分类的算法，那为什么不叫逻辑分类？因为逻辑回归算法是基于多元线性回归的算法（多元线性回归：yw0x0w1x1.....wnxn)。正因为…...

编程日记 2025/5/20 9:08:28

深入 Linux 内核：GPU Runtime Suspend 源码和工作流程全面分析

这是系列文章中第二篇，我们将分析完整的 Linux runtime suspend 操作流程，以 Vivante GPU 为例，展示开发者如何通过内核程序实现和调试 runtime PM 机制。一、内核中的 Runtime PM 工作流程概览当调用者执行: pm_runtime_put(dev);时&…...

编程日记 2025/5/25 8:45:04

深入理解 this 指向与作用域解析

引言 JavaScript 中的 this 关键字的灵活性既是强大特性也是常见困惑源。理解 this 的行为对于编写可维护的代码至关重要，但其动态特性也会让我们感到困惑。与大多数编程语言不同，JavaScript 的 this 不指向函数本身，也不指向函数的词法作…...

编程日记 2025/5/26 22:17:13

c++20引入的三路比较操作符＜=＞

目录一、简介二、三向比较的返回类型 2.1 std::strong_ordering 2.2 std::weak_ordering 2.3 std::partial_ordering 三、对基础类型的支持四、自动生成的比较运算符函数 4.1 std::rel_ops的作用 4.2 使用<> 五、兼容他旧代码一、简介 c20引入了三路比较操…...

编程日记 2025/5/29 10:48:22

Spring框架（三）

目录一、JDBC模板技术概述 1.1 什么是JDBC模板二、JdbcTemplate使用实战 2.1 基础使用（手动创建对象） 2.2 使用Spring管理模板类 2.3 使用开源连接池（Druid） 三、模拟转账开发 3.1 基础实现 3.1.1 Service层 3.1.2 Da…...

编程日记 2025/5/29 13:11:42

CS016-4-unity ecs

【37】将系统转换为任务 Converting System to Job 【Unity6】使用DOTS制作RTS游戏|17小时完整版|CodeMonkey|【37】将系统转换为任务 Converting System to Job_哔哩哔哩_bilibili a. 将普通的方法，转化成job。第一个是写一个partial struct xxx；第二…...

编程日记 2025/5/19 10:26:33

CMU-15445(4)——PROJECT#1-BufferPoolManager-Task#2

PROJECT#1-BufferPoolManager Task #2 - Disk Scheduler 在前一节我实现了 TASK1 并通过了测试，在本节中，我将逐步实现 TASK2。如上图，Page Table（页表）通过哈希表实现，用于跟踪当前存在于内存中的页&am…...

编程日记 2025/5/19 11:16:29

[原创](计算机数学)(The Probability Lifesaver)(P10): 生日概率问题.

[作者] 常用网名: 猪头三出生日期: 1981.XX.XX 企鹅交流: 643439947 个人网站: 80x86汇编小站编程生涯: 2001年~至今[共24年] 职业生涯: 22年开发语言: C/C++、80x86ASM、Object Pascal、Objective-C、C#、R、Python、PHP、Perl、开发工具: Visual Studio、Delphi、XCode、…...

编程日记 2025/5/30 11:50:46

计算机组成原理——数据的表示

2.1数据的表示整理自Beokayy_ 1.进制转换十六进制与二进制的转换一位十六进制等于四位二进制四位二进制等于一位十六进制 0x173A4C0001 0111 0011 1010 0100 1100 十六进制与十进制的转换十六转十：每一位数字乘以相应的16的幂再相加十转十六&#xff1a…...

编程日记 2025/5/29 18:30:38

源码：处理文件格式和字符集的相关代码（3-3）

总入口：源码：处理文件格式和字符集的相关代码（3-1）-CSDN博客目录六、预览（正确显示文本文件） 6.1 总体逻辑 6.2 二进制显示 6.3 文本显示六、预览（正确显示文本文件） 6.1 总…...

编程日记 2025/5/23 3:12:50

Spring MVC 对 JavaWeb 的优化：从核心组件到注解

Spring MVC 功能组件与注解对 JavaWeb 的优化文章介绍： SpringMVC对比JavaWeb优势，Spring MVC 通过引入功能组件和注解，从多个维度对传统 JavaWeb 开发进行了优化，显著提升了开发效率和代码可维护性。以下是关键优化点的详细对…...

编程日记 2025/5/31 7:35:27

Mysql数据库详解

在cmd中选择数据库操作用 USE test_db; 相关概念 Sql是操作关系型数据库的编程语言关系型数据库：建立在关系模型基础上，由多张相互连接的二维表组成的数据库语法 sql语法分类 DDL-数据库操作创建：CREATE DATABASE db_name;创建完整…...

编程日记 2025/5/28 16:06:08

R1 快开门式压力容器操作证备考练习题及答案

R1 快开门式压力容器操作证备考练习题及答案判断题 1、快开门式压力容器的快开门应设计成有延时功能的联锁装置。（√） 解析：延时功能的联锁装置可以防止在容器内有压力时过早开启快开门，避免发生危险，保障设备和人…...

编程日记 2025/5/30 1:18:24

python打卡训练营Day27

作业： 编写一个装饰器 logger，在函数执行前后打印日志信息（如函数名、参数、返回值） logger def multiply(a, b):return a * bmultiply(2, 3) # 输出: # 开始执行函数 multiply，参数: (2, 3), {} # 函数 multiply …...

编程日记 2025/5/28 7:02:31