算法训练营第24天回溯（组合）

回溯（组合）

模板

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

在这里插入图片描述

在这里插入图片描述

第77题. 组合

力扣题目链接(opens new window)

题目

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4],]

解答

正常方法（不够快，遍历了许多没必要的枝）

一个递归就相当于嵌套了一个for（每个递归都是一个分而治之的过程，第一个for是为了取第一个数，之后每次递归都再取一个）

在这里插入图片描述

class Solution {
	List<List<Integer>> results = new ArrayList<>();
	List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
		backtracking(n,k,1);
		return results;
    }

	void backtracking(int n, int k,int index){
		if (path.size() == k){
			results.add(new ArrayList<>(path));
			return;
		}

		for (int i = index; i <= n; i++) {//每个for都是一个单独的横向分支
			path.add(i);
			backtracking(n,k,i + 1);//每个递归都是纵向枝
			path.remove(path.size() - 1);
		}
	}
}
剪枝优化

只是修改了for的终止条件，去除没用的枝

在这里插入图片描述

  1. 已经选择的元素个数：path.size();
  2. 所需需要的元素个数为: k - path.size();
  3. 列表中剩余元素（n-i） >= 所需需要的元素个数（k - path.size()）
  4. 在集合n中至多要从该起始位置 : i <= n - (k - path.size()) + 1，开始遍历
    • 例：如果n = 4， k = 4， 那么只有index = 1这条枝需要保留，i<= 1， 因为此时path为空，所以k - path = 4，故n - (k - path.size()) + 1
class Solution {
	List<List<Integer>> results = new ArrayList<>();
	List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
		backtracking(n,k,1);
		return results;
    }

	void backtracking(int n, int k,int index){
		if (path.size() == k){
			results.add(new ArrayList<>(path));
			return;
		}

		for (int i = index; i <= n - (k - path.size()) + 1; i++) {//如果n = 4， k = 4， 那么只有index = 1这条枝需要保留，i<= 1， 因为此时path为空，所以k - path = 4，故n - (k - path.size()) + 1
			path.add(i);
			backtracking(n,k,i + 1);
			path.remove(path.size() - 1);
		}
	}
}

216.组合总和III

力扣题目链接(opens new window)

题目

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

  • 所有数字都是正整数。
  • 解集不能包含重复的组合。

示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]

示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]

解答

涉及到了两处剪枝

  1. 如果目前相加的和已经大于sum，并且没有达到k个元素，也就意味着后面再加只会更大，剪枝就行了

    if (path.size() == k || sum >= n){//sum >= n是为了求和时的剪枝
    if (sum == n && path.size() == k)
        results.add(new ArrayList<>(path));
    return;
}
//等价于
if (sum > n) return;//对sum剪枝

if (sum == n && path.size() == k){
    results.add(new ArrayList<>(path));
    return;
}

  2. 对个数进行剪枝，与上一个题一样

    for (int i = index; i <= 9 - (k - path.size()) + 1; i++) 
//等价于
if (path.size() > k ) return;//对数量剪枝

class Solution {
	List<List<Integer>> results = new ArrayList<>();
	List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
		backtracking(k,n,1,0);
		return results;
    }

	void backtracking(int k,int n,int index,int sum){
		if (path.size() == k || sum >= n){//sum >= n是为了求和时的剪枝
			if (sum == n && path.size() == k)
				results.add(new ArrayList<>(path));
			return;
		}

		for (int i = index; i <= 9 - (k - path.size()) + 1; i++) {//9 - (k - path.size()) + 1是为了数量不够时的剪枝
			path.add(i);
			backtracking(k,n,i + 1,sum + i);
			path.remove(path.size() - 1);
		}
	}
}

等价形式

class Solution {
	List<List<Integer>> results = new ArrayList<>();
	List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
		backtracking(k,n,1,0);
		return results;
    }

	void backtracking(int k,int n,int index,int sum){

		if (path.size() > k ) return;//对数量剪枝

		if (sum > n) return;//对sum剪枝

		if (sum == n && path.size() == k){
			results.add(new ArrayList<>(path));
			return;
		}

		for (int i = index; i <= 9; i++) {
			path.add(i);
			backtracking(k,n,i + 1,sum + i);
			path.remove(path.size() - 1);
		}
	}
}

17.电话号码的字母组合

力扣题目链接(opens new window)

题目

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

在这里插入图片描述

示例:

  • 输入：“23”
  • 输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

说明：尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

解答

有几个字母深度就是几

注意回溯后的组合一定是无序的，因为会先把最后一个全部找完，再找前一个（不涉及顺序，才能这么回溯）

例：

测试用例：“234”

结果：[adg, adh, adi, aeg, aeh, aei, afg, afh, afi, bdg, bdh, bdi, beg, beh, bei, bfg, bfh, bfi, cdg, cdh, cdi, ceg, ceh, cei, cfg, cfh, cfi]

  1. adg：2的第一个，3的第一个，4的第一个，此时index + 1= 3，达到结束条件，将adg加入
  2. 将最后一个g弹出，进入index = 3的for循环，再次将4对应的第二个h放入path，然后将adh加入
  3. 同理，将adi加入
  4. 此时第三个for已经结束，跳出该循环，第三个递归结束，此时index = 2，并且当前的path中只有ad，然后执行回溯，d再次被弹出
  5. 进入第二个for的第二层，即将3对应的第二个元素e加入，进入递归，此时index没达到4，所以继续进入下一层递归，将4的第一个元素g再加入，即得到aeg
  6. 依次类推
class Solution {
	List<String> result = new ArrayList<>();
	StringBuffer path = new StringBuffer();
    public List<String> letterCombinations(String digits) {
		if (Objects.equals(digits, "") || Objects.equals(digits, " "))
			return result;
		Map<Character,String> map = new HashMap<>();
		map.put('2', "abc");
		map.put('3', "def");
		map.put('4', "ghi");
		map.put('5', "jkl");
		map.put('6', "mno");
		map.put('7', "pqrs");
		map.put('8', "tuv");
		map.put('9', "wxyz");
		backtracking(digits,map,0);
		return result;
    }
	void backtracking(String digits,Map<Character,String> map,int index){
		if (index == digits.length()){
			result.add(path.toString());
			return;
		}

		String element = map.get(digits.charAt(index));
		for (int i = 0; i < element.length(); i++) {
			path.append(element.charAt(i));
			backtracking(digits,map,index + 1);
			path.deleteCharAt(path.length() - 1);//一定是无序的
		}
	}
}

39. 组合总和

力扣题目链接(opens new window)

题目

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

  • 所有数字（包括 target）都是正整数。
  • 解集不能包含重复的组合。

示例 1：

  • 输入：candidates = [2,3,6,7], target = 7,
  • 所求解集为： [ [7], [2,2,3] ]

示例 2：

  • 输入：candidates = [2,3,5], target = 8,
  • 所求解集为： [ [2,2,2,2], [2,3,3], [3,5] ]

解答

巨大误区：

必须要有startIndex参数，只是startIndex的传入参数根据情况不同而不同，但是必须要有，如果没有就会出现重复的元素，也就是可能出现在这里插入图片描述
这种情况，因为如果使用下面的代码，

		for (int i = 0; i < candidates.length; i++) {
			path.add(candidates[i]);
			backtracking(candidates, target, sum + candidates[i], i);
			path.removeLast();//sum在当前这一轮中没有变，也就是相当于已经进行了回溯
		}

也就相当于每次都是从0开始，也就意味着当当前递归函数结束，返回上一层时，上一层重新进入下一层的递归树时，还是会遍历之前已经遍历过的元素，导致重复组合的产生

例：[2,3,6,7] 7

  1. 2 2 2 2 remove
  2. 2 2 2 3 remove
  3. 2 2 2 6 remove
  4. 2 2 2 7 remove
  5. 2 2 3 return
  6. 2 2 6 remove
  7. 2 2 7 remove
  8. 2 3 2出现了重复，因为在当这一轮来说，下一层递归不应该在遍历当前遍历的元素之前的元素，因为在之前已经遍历过了，所以就会出现重复的组合

正确代码应该是

		for (int i = startIndex; i < candidates.length; i++) {
			path.add(candidates[i]);
			backtracking(candidates, target, sum + candidates[i], i);
			path.removeLast();//sum在当前这一轮中没有变，也就是相当于已经进行了回溯
		}

还应该注意必须要排序，因为如果不排序那么使用if (sum > target) return;来剪枝就是错误的

正确代码
class Solution {
	List<List<Integer>> result = new ArrayList<>();
	LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
		Arrays.sort(candidates);
		backtracking(candidates,target,0,0);
		return result;
    }

	void backtracking(int[] candidates,int target,int sum,int startIndex){
		if (sum > target) return;//剪枝

		if (sum == target){
			result.add(new LinkedList<>(path));
			return;
		}
		for (int i = startIndex; i < candidates.length; i++) {
			path.add(candidates[i]);
			backtracking(candidates, target, sum + candidates[i], i);
			path.removeLast();//sum在当前这一轮中没有变，也就是相当于已经进行了回溯
		}
	}
}
总结
  1. 一定要是有index，不要想当然的使用for，导致重复元素的产生
  2. 一定要排序，否则剪枝会有问题

40.组合总和II

力扣题目链接(opens new window)

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明： 所有数字（包括目标数）都是正整数。解集不能包含重复的组合。

  • 示例 1:
  • 输入: candidates = [10,1,2,7,6,1,5], target = 8,
  • 所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]
  • 示例 2:
  • 输入: candidates = [2,5,2,1,2], target = 5,
  • 所求解集为:
[
  [1,2,2],
  [5]
]

解答

在这里插入图片描述

树枝去重

backtracking(candidates,target,sum + candidates[i],i + 1);使用i+1来防止树枝遍历相同的元素，也就是防止出现重复元素（由于每个元素只能出现一次，所以为i+1，否则就像上一个题一样为i）

树层去重

if (i > startIndex && candidates[i] == candidates[i - 1]) continue;对于同一层的元素，如果两个元素相同，就直接跳过该轮，否则也会出现重复元素

class Solution {
	List<List<Integer>> result = new ArrayList<>();
	LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
		Arrays.sort(candidates);
		backtracking(candidates,target,0,0);
		return result;
    }
	void backtracking(int[] candidates, int target , int sum, int startIndex){
		if (sum > target) return;

		if (sum == target){
			result.add(new ArrayList<>(path));
			return;
		}

		for (int i = startIndex; i < candidates.length; i++) {
			if (i > startIndex && candidates[i] == candidates[i - 1])
				continue;//因为已经排序过，所以要保证同一层的元素不相同，如果相同直接跳过
			//也就是对于path中索引相同位置的元素不能两次一致，这样可能会出现重复的组合
			path.add(candidates[i]);
			backtracking(candidates,target,sum + candidates[i],i + 1);
			path.removeLast();
		}
	}
}

求和总结

  1. 对于不包含重复元素的集合，要想防止出现元素重复的组合，即[2 , 3] [3 , 2]为重复元素的组合，就要使用startIndex来限定 backtracking(candidates,target,sum + candidates[i],i + 1);

    1. 如果是允许同一个元素在组合中多次出现，则使用 backtracking(candidates,target,sum + candidates[i],i + 1);

  2. 对于包含重复元素的集合，除了要是有startIndex外，还需要对树层元素进行判断，否则如果是[1 ,1,2,3]，target = 3，就会出现两个相同的[1,2]，因为对于第一层会遍历两次，使用if (i > startIndex && candidates[i] == candidates[i - 1]) continue;解决

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

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

相关文章

OpenHarmony南向统一编译的docker镜像来了

OpenHarmony南向统一编译的docker镜像来了

由于我自己的南向设备开发平台的需求&#xff0c;我将当前几个不同的 docker 镜像版本进行了整合&#xff0c;经过一段时间的攻关和验证&#xff0c;目前整合已完成&#xff0c;新版本的 Dockerfile 如下&#xff0c;这个不是公共需求&#xff0c;所以没有提交主干&#xff0c;…
阅读更多...
SAP SD学习笔记03 - SD模块中的主数据

SAP SD学习笔记03 - SD模块中的主数据

上一章讲了SD中的组织单位和SD的简单流程。 SAP SD学习笔记02 - 销售流程中的组织单位-CSDN博客 SAP SD学习笔记01 - 简单走一遍SD的流程&#xff1a;受注&#xff0c;出荷&#xff0c;请求-CSDN博客 这一章讲SD中的主数据&#xff1a; - 得意先Master&#xff08;客户&…
阅读更多...
Springboot 大事务问题的常用优化方案

Springboot 大事务问题的常用优化方案

&#x1f3f7;️个人主页&#xff1a;牵着猫散步的鼠鼠 &#x1f3f7;️系列专栏&#xff1a;Java全栈-专栏 &#x1f3f7;️个人学习笔记&#xff0c;若有缺误&#xff0c;欢迎评论区指正 目录 1.前言 2.什么是大事务 3.解决办法 3.1.少用Transactional注解 3.2..将查询…
阅读更多...
贝康医疗交出2023年答卷：收入增长超47%，并购夯实领头羊地位

贝康医疗交出2023年答卷：收入增长超47%，并购夯实领头羊地位

2023年6月&#xff0c;国家医保局印发《辅助生殖类医疗服务价格项目立项指南&#xff08;试行&#xff09;》&#xff0c;将全国各地原有的37项辅助生殖类项目分类整合为12项。 据北京日报统计&#xff0c;国家医保局截至目前已指导21个省份对照立项指南整合辅助生殖类项目&am…
阅读更多...
ChatGPT在日常生活与工作中的应用，以及Hulu AI 的探索之旅

ChatGPT在日常生活与工作中的应用，以及Hulu AI 的探索之旅

ChatGPT在日常生活与工作中的应用&#xff0c;以及Hulu AI 的探索之旅 &#x1f4ac;ChatGPT 的多面应用&#x1f4ac;Hulu AI&#xff1a;一个AI工具聚合平台的探索平台优势为何选择Hulu AI&#xff1f;珍稀优惠 &#x1f4ac;结束语 在数字化快速发展的当下&#xff0c;人工智…
阅读更多...
详解Spring event如何优雅实现系统业务解耦、实现原理及使用注意项

详解Spring event如何优雅实现系统业务解耦、实现原理及使用注意项

1.概述 在我们平时的项目业务系统开发过程中&#xff0c;一个需求功能的业务逻辑经常出现主线业务和副线业务之分。比如&#xff0c;在当下移动端电商app进行注册账号操作&#xff0c;注册成功之后会发送短信、邮箱、站内信等通知&#xff0c;发放红包活动抵用券&#xff0c;推…
阅读更多...
20210620 1+X 中级实操考试（id：2496）

20210620 1+X 中级实操考试（id：2496）

完成实体类 Student public class Student {private String name;//学生姓名private String pwd;//学生密码public Student(String name, String pwd) {this.name name;this.pwd pwd;}public Student() {}//已经提供Student类的属性&#xff0c;补充完成该类的有参&#xff…
阅读更多...
谁才是国内的“OpenAI”？国产大模型五虎之——百川智能

谁才是国内的“OpenAI”？国产大模型五虎之——百川智能

前言&#xff1a; 在上一篇大模型五虎的文章中&#xff0c;我们介绍了国内估值最高的大模型企业——智谱AI&#xff0c;它们拥有自研的 GLM&#xff08;General Language Model&#xff09;算法框架&#xff0c;从最初追逐OpenAI的脚步&#xff0c;到“不愿做国内的OpenAI”&am…
阅读更多...
【2024.4.11练习】国际象棋

【2024.4.11练习】国际象棋

题目描述 题目思路 棋盘类问题是一类典型的状态压缩dp问题&#xff0c;将0设为不摆放象棋&#xff0c;1设为摆放象棋。这样棋盘的每一列都可以变成01的序列。每一列有8个格子&#xff0c;所以每列总共有种摆放情况。为了完成递推&#xff0c;需要写出以下功能的预处理函数 ini…
阅读更多...
如何安装PyFluent

如何安装PyFluent

0.什么是PyFluent? 官方介绍如下&#xff1a; PyFluent 是 PyAnsys 生态系统的一部分&#xff0c; 允许您在所选的 Python 环境中结合使用 Fluent 与其他 PyAnsys 库和外部 Python 库一起使用。 PyFluent 实现了客户端-服务器体系结构。它使用谷歌遥控器 过程调用或 gRPC 接…
阅读更多...
Cyber Weekly #1

Cyber Weekly #1

赛博新闻 1、弱智吧竟成最佳中文AI训练数据&#xff1f;&#xff01;中科院等&#xff1a;8项测试第一&#xff0c;远超知乎豆瓣小红书 使用弱智吧数据训练的大模型&#xff0c;跑分超过百科、知乎、豆瓣、小红书等平台&#xff0c;甚至是研究团队精心挑选的数据集。弱智吧数…
阅读更多...
审查元素时，hover等伪元素，只会在鼠标悬停在对应元素上时生效。一旦鼠标移开，样式就会消失，已解决

审查元素时，hover等伪元素，只会在鼠标悬停在对应元素上时生效。一旦鼠标移开，样式就会消失，已解决

最近遇到个小小的问题 当el-input 设置cleable属性的时候&#xff0c;鼠标移入输入框内&#xff0c;会有个清除的图标 输入框的内容居右显示&#xff0c;导致清除的图标和内容重叠了 通过控制台查看元素&#xff0c;只有在鼠标悬停在对应元素上时生效。一旦鼠标移开&#xf…
阅读更多...
JR-SMD201网络直播解码器

JR-SMD201网络直播解码器

详细介绍&#xff1a; JR-SMD201网络直播解码器&#xff0c;支持AVS/H.265/H.264/MPEG2解码&#xff0c;支持IP输入&#xff0c;支持1080P/1080I/720P/576I/480I多种分辨率&#xff0c;支持DRA/AC3/EAC3/AAC/MPEG等音频。 产品特点 支持多种输入方式IP 接口丰富&#xff0c;CV…
阅读更多...
ELK（Elasticsearch+Logstash+Kibana）日志分析系统

ELK（Elasticsearch+Logstash+Kibana）日志分析系统

目录 前言 一、ELK日志分析系统概述 1、三大组件工具介绍 1.1 Elasticsearch 1.1.1 Elasticsearch概念 1.1.2 关系型数据库和ElasticSearch中的对应关系 1.1.3 Elasticsearch提供的操作命令 1.2 Logstash 1.2.1 Logstash概念 1.2.2 Logstash的主要组件 1.2.3 Logsta…
阅读更多...
【MATLAB源码-第8期】基于matlab的DPSK的误码率仿真，差分编码使用汉明码（hanming）。

【MATLAB源码-第8期】基于matlab的DPSK的误码率仿真，差分编码使用汉明码（hanming）。

1、算法描述 差分相移键控常称为二相相对调相&#xff0c;记作2DPSK。它不是利用载波相位的绝对数值传送数字信息&#xff0c;而是用前后码元的相对载波相位值传送数字信息。所谓相对载波相位是指本码元初相与前一码元初相之差。差分相移键控信号的波形如概述图所示。 假设相对…
阅读更多...
前端开发攻略---轻松实现排序功能：利用JavaScript创建直观的拖拽排序体验

前端开发攻略---轻松实现排序功能：利用JavaScript创建直观的拖拽排序体验

拖拽事件主要包括以下几种&#xff1a; dragstart&#xff08;拖拽开始&#xff09;&#xff1a;当用户开始拖拽一个元素时触发&#xff0c;通常在被拖拽的元素上绑定此事件。在该事件的处理函数中&#xff0c;可以设置被拖拽元素的一些属性或数据。 drag&#xff08;拖拽移动…
阅读更多...
【Shell语言学堂】函数调用练习

【Shell语言学堂】函数调用练习

Shell编程的函数 Shell中的函数概念优点标准shell函数定义函数调用实战案例1、实现画菱形2、将画正三角和倒三角拆分为两个函数3、将菱形的代码拆解成1个函数&#xff1a;画空格和*号4、将十进制的IP地址转为二进制5、选做&#xff1a;将二进制的IP地址转为十进制 Shell中的函数…
阅读更多...
多通道电路PCB如何布局布线 - Altium Designer模块复用功能介绍

多通道电路PCB如何布局布线 - Altium Designer模块复用功能介绍

原文出自微信公众号【小小的电子之路】 电路设计的过程中难免会遇到多通道电路设计&#xff0c;在通道数较少的情况下&#xff0c;可以多花点时间&#xff0c;一个通道一个通道地布局布线&#xff0c;但是在通道数特别多的情况下&#xff0c;这种方法就不现实了&#xff0c;好在…
阅读更多...
掼蛋的5-10原则

掼蛋的5-10原则

掼蛋的5-10原则指的是在掼蛋游戏重&#xff0c;所有的5被打出后&#xff0c;牌面上就不可能有9以下的小顺子&#xff1b;而当10都被打出后&#xff0c;6以上到A的顺子也没有了。这就被掼蛋玩家用来判断手中顺子的实际价值。 前期注意观察5和10的出牌情况。如果起手就有较多的5和…
阅读更多...
gradio简单搭建——关键词简单筛选【2024-4-11优化】

gradio简单搭建——关键词简单筛选【2024-4-11优化】

gradio简单搭建——关键词简单筛选[2024-4-11 优化] 新的思路&#xff1a;标签自动标注界面搭建优化数据处理与生成过程交互界面展示 新的思路&#xff1a;标签自动标注 针对通过关键词&#xff0c;在文本数据中体现出主体的工作类型这一任务&#xff0c;这里使用展示工具grad…
阅读更多...
最新文章

Copyright @ 2022~2023