Leetcode 40 组合总和 II

题意理解:

  1.         每个数字在每个组合中只能使用 一次 
  2.         数字可以重复——>难点(如何去重)
  3.         每个组合和=target

        求组合,对合限制,考虑回溯的方法。——将其抽象为树结构。

        树的宽度——分支大小

        树的深度——最长的组合(和=target)

  去重难点:

        根据《代码随想录》关于树层去重的引入:

        第一个位置选2,再次选2的话,下面的分支回出现重复的[2,3]组合。

        实际上保留第一个分支,之后同一位置相同的数值选项可以剪除。

        用used[]数组来维护是否被访问的状态。

        

回溯的方法:

        1.确定返回值+参数列表

        2.确定终止条件|剪枝条件

        3.单层逻辑|回溯操作

1.暴力回溯+剪枝优化

考虑返回值一般为void, 参数包含数组,和目标值,当前数值指示下标

终止条件: sum>=4,特别的sum==4时收集结果。

单层递归逻辑:一定要对sum和path、used数组做好回溯操作。

数层剪枝:candidates[i-1]==candidates[i]遇到重复值

        used[i-1]=true:表示上一个重复的值,在该组合内被用到。

        used[i - 1] == false:表示上一个重复值在该组合内没有用到,应该是同一树层用到——即数层重复,剪枝。

List<List<Integer>> result=new ArrayList<>();
    LinkedList<Integer> path=new LinkedList<>();
    int sum=0;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        boolean[] used=new boolean[candidates.length];
        Arrays.sort(candidates);
        Arrays.fill(used, false);
        backtrackig(candidates,target,0,used);
        return result;
    }
    public void backtrackig(int[] candidates, int target,int startIndex,boolean[] used){

        //终止|剪枝
        if(sum>target) return;
        else if (sum==target) {
            result.add(new ArrayList<>(path));
            return;
        }
        //单层递归逻辑
        for(int i=startIndex;i<candidates.length;i++){
            //数层剪枝
            if(i!=0&&candidates[i-1]==candidates[i]&&used[i-1]==false) continue;
            path.add(candidates[i]);
            sum+=candidates[i];
            used[i]=true;
            backtrackig(candidates,target,i+1,used);
            path.removeLast();
            sum-=candidates[i];
            used[i]=false;
        }
    }

注意两个特殊的地方:

Arrays.sort(candidates);//数组排序

Arrays.fill(used, false);//数组填充,实际上该数组默认也是false.

2.分析

时间复杂度:O(2^{n} \times n)

空间复杂度:O(n)

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

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

相关文章

分配栈空间的三种方式(基于适配qemu的FreeRTOS分析)

1、定义全局的数组 定义的全局数组属于bss段&#xff0c;相当于把bss段的一部分作为栈空间&#xff0c;栈空间的大小就是数组的大小如果把栈空间放在bss段&#xff0c;则在bss段清零时会多清零一段地址空间 2、在链接脚本中指定 用链接脚本在所有段的后面增加stack段&#xff…

Altair Radioss碰撞 安全与冲击 衡祖仿真

Altair Radioss是解决瞬态加载工况下非线性问题的领先的结构分析求解器。其具备高扩展性、高品质、高鲁棒性&#xff0c;以及诸多功能&#xff1a;多域求解技术、高级材料功能(复合材料)等。Radioss求解器被广泛应用于汽车、航空航天、电子/家电、包装、轨道机车、生物医疗、能…

数据结构(C语言)

链表 链表的基本能操作 #include <stdbool.h> #include <stdio.h> #include <stdlib.h>//链表的接口 typedef struct node_s{int val;struct node_s*next; } Node; typedef struct linkedlist_s{Node* head;Node* tail;int size; }LinkedList;//创建空链表…

腾讯物联网平台之规则引擎

1.腾讯物联网平台简介 腾讯云物联网开发平台&#xff08;IoT Explorer&#xff09;为客户提供便捷的物联网开发工具与服务&#xff0c;助力客户更高效的完成设备接入&#xff0c;并为客户提供物联网应用开发及场景服务能力&#xff0c;帮助客户高效、低成本构建物联网应用。  …

Java LeetCode篇-二叉树经典解法(实现:判断平衡二叉树、找两个节点最近的祖先等)

&#x1f525;博客主页&#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞&#x1f44d;收藏⭐评论✍ 文章目录 1.0 平衡二叉树 1.1 实现判断平衡二叉树的思路 1.2 代码实现判断平衡二叉树 2.0 二叉树的层序遍历 2.1 实现二叉树层序遍历的思路 2.2 代码实现二叉树层序遍历 3.0 …

Linux开发工具--vim

Linux开发工具--vim 一、vim的基本概念二、常见命令三、简单配置vim配置文件的位置常用配置选项&#xff0c;用来测试使用插件 一、vim的基本概念 vim编辑器&#xff0c;只负责写代码&#xff0c;vim是一款多模式的编辑器 vim的三种模式(其实有好多模式&#xff0c;目前掌握这…

PbootCMS 前台RCE漏洞复现

0x01 产品简介 PbootCMS是全新内核且永久开源免费的PHP企业网站开发建设管理系统,是一套高效、简洁、 强悍的可免费商用的PHP CMS源码,能够满足各类企业网站开发建设的需要 0x02 漏洞概述 PbootCMS v<=3.1.6版本中存在模板注入,攻击者可构造特定的链接利用该漏洞,执行…

跟着我学Python基础篇:06.列表

往期文章 跟着我学Python基础篇&#xff1a;01.初露端倪 跟着我学Python基础篇&#xff1a;02.数字与字符串编程 跟着我学Python基础篇&#xff1a;03.选择结构 跟着我学Python基础篇&#xff1a;04.循环 跟着我学Python基础篇&#xff1a;05.函数 目录 往期文章1. 列表的基本…

ES-分析器

分析器 两种常用的英语分析器 1 测试工具 #可以通过这个来测试分析器 实际生产环境中我们肯定是配置在索引中来工作 GET _analyze {"text": "My Moms Son is an excellent teacher","analyzer": "english" }2 实际效果 比如我们有下…

win10脚本 | 使用 Word 自动化对象模型找出指定路径下含有特定内容的.docx

场景 今年的实验日志被我放在这样一个文件夹下&#xff0c;每个月下是每天具体的.docx文件&#xff0c;里面记录了我的一些实验操作步骤。现在我需要补充一个实验&#xff0c;用到一个名为chatunitest的插件&#xff0c;但是这是很久之前做的事情了&#xff0c;我无法判断是哪…

PHP 之道(PHP The Right Way 中文版)

PHP 之道&#xff08;PHP The Right Way 中文版&#xff09;

2022年重庆市职业院校技能大赛高职组“信息安全管理与评估”赛项竞赛任务书-试题01

信息安全管理与评估 第一阶段 网络平台搭建与设备安全防护 目 录 第一阶段竞赛项目试题 介绍 所需的设备、机械、装置和材料 评分方案 注意事项 项目和任务描述 1.网络拓扑图 2.IP地址规划表 工作任务 任务1&#xff1a;网络平台搭建 任务2&#xff1a;网络安全设备…

Find My手链|苹果Find My技术与手链结合,智能防丢,全球定位

手链是一种首饰&#xff0c;配戴在手腕部位&#xff0c;多为金银等金属制品&#xff0c;也有矿石、水晶等制的。手链是链状的&#xff0c;以祈求平安&#xff0c;镇定心志和美观为主要用途。手链可以展示个人的风格和品味&#xff0c;通过选择不同材质、款式和颜色的手链&#…

这样的性能测试面试题,测试开发来了都不见得会把?

14.1 性能测试怎么测试 性能测试其实就是通过自动化工具模拟多种正常、峰值以及异常负载来对系统的各项性能指标进 行测试。负载测试和压力测试都属于性能测试&#xff0c;二者可结合使用。 性能指标主要有平均响应时间、90%响应时间、吞吐量、吞吐率&#xff0c;每秒事务数&am…

新版Spring Security6.2架构 (三) - Authorization

前言 书接上文&#xff0c;在经过了authentication后就是authorization了&#xff0c;本文还是对官网文档authorization的一个架构翻译和个人理解&#xff0c;后续的博客在写具体使用例子&#xff0c;从数据中认证&#xff0c;融合authentication和authorization的概念。 Aut…

【论文解读】Accelerating motion estimation by genetic algorithm approach in x265

时间&#xff1a;2018 级别&#xff1a;SCI 机构&#xff1a;College of Engineering Pune 摘要&#xff1a; 在过去 20 年&#xff0c;在视频编码和压缩领域&#xff0c;研究人员提出了几种减少运动估计的计算量和时间的技术&#xff0c;本文提出了一种基于遗传算法初始种群确…

电脑ffmpeg.dll丢失如何修复?3个详细修复的教程分享

在计算机使用过程中&#xff0c;我们经常会遇到一些错误提示&#xff0c;其中之一就是“ffmpeg.dll丢失”。ffmpeg.dll是FFmpeg多媒体框架中的一个重要组件&#xff0c;它负责处理音频和视频的编解码。当这个文件丢失或损坏时&#xff0c;可能会导致一些应用程序无法正常运行。…

2023年【G2电站锅炉司炉】报名考试及G2电站锅炉司炉考试资料

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 G2电站锅炉司炉报名考试根据新G2电站锅炉司炉考试大纲要求&#xff0c;安全生产模拟考试一点通将G2电站锅炉司炉模拟考试试题进行汇编&#xff0c;组成一套G2电站锅炉司炉全真模拟考试试题&#xff0c;学员可通过G2电…

如何有效利用餐厅预约小程序推广餐厅品牌

随着餐饮行业竞争的加剧&#xff0c;餐厅订座预约成为了吸引顾客的一种重要方式。而微信小程序作为移动互联网的重要入口之一&#xff0c;为餐厅提供了一个方便快捷的预约平台。本文将介绍如何使用乔拓云平台等第三方小程序制作平台来开发餐厅订座预约微信小程序。 首先&#x…

进程、容器与虚拟机的区别

进程、容器与虚拟机 参考&#xff1a;关于进程、容器与虚拟机的区别&#xff0c;你想知道的都在这&#xff01; 进程、容器与虚拟机的结构图 进程 介绍 进程是一个正在运行的程序&#xff0c;它是一个个可执行文件的实例。当一个可执行文件从硬盘加载到内存中的时候&#xf…