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

Javascript算法——回溯算法(组合问题)

相关资料来自《代码随想录》,版权归原作者所有,只是学习记录
在这里插入图片描述

回溯

回溯模板

void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {处理节点;backtracking(路径,选择列表); // 递归回溯,撤销处理结果}
}

回溯搜索过程可以概括为一棵"树"

在这里插入图片描述
三数之和 四数之和 也有点类似求满足指定条件的数组

组合问题

组合与排列的区别

排列:排列是指从一组元素中选择若干个元素并考虑顺序,也就是说 [1, 2] 和 [2, 1] 是不同的排列。

组合:组合是指从一组元素中选择若干个元素,但不考虑顺序,因此 [1, 2] 和 [2, 1] 视为相同的组合。

1. 在这里插入图片描述————————————————————————————————在这里插入图片描述

核心:
1.递归,设置回溯函数参数(index),避免重复组合[1,2]与[2,1]
2.剪枝:i<=_n-(_k-path.length)+1,保证还有足够多元素(此题)
3.利用slice方法浅拷贝数组,而不是直接加result.push(path.slice())在这里插入图片描述

/*** @param {number} n* @param {number} k* @return {number[][]}*/
var combine = function(n, k) {let result=[],path=[];let backtracking=(_n,_k,startIndex)=>{//终止条件if(path.length===_k){result.push(path.slice());return;}//循环本层集合元素//剪枝操作:i<=_n-(_k-path.length)+1for(let i=startIndex;i<=_n-(_k-path.length)+1;i++){path.push(i);//递归backtracking(_n,_k,i+1);//回溯操作path.pop();}};backtracking(n,k,1);return result  
};

2
在这里插入图片描述
———————————————————————————————

核心:
1.不重复,与上类似回溯函数设置一个索引参数index
2.数字1-9,想着去生成数组?->遍历就行for(let i=startIndex;i<9;i++),无需额外定义

/*** @param {number} k* @param {number} n* @return {number[][]}*/
var combinationSum3 = function(k, n) {//确定参数和返回值//参数:k为递归树的层数,即数组path.length===k时就收集结果了!//n为收集数组元素和let result=[],path=[];let sum=0;let backtracking=(_k,_n,startIndex)=>{//确定递归终止条件if(path.length===_k){//数组元素之和不为n,直接返回if(sum===_n){//path.slice()!!!浅拷贝//[...path]result.push(path.slice());}return;}for(let i=startIndex;i<9;i++){sum+=i;path.push(i);//递归backtracking(_k,_n,i+1);//回溯sum-=i;path.pop();}}backtracking(k,n,1);return result; 
};

3.
在这里插入图片描述

核心
1.字母映射:用JS中数组就行!let letterMap=["","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"];
2.还是利用数组存遍历的元素,返回结果时对结果做处理就行result.push(path.join(""));
3.本问题是对多个集合做组合问题,且每个集合中元素唯一。直接再遍历时处理就行!const v of letterMap[digits[_diIndex]]

/*** @param {string} digits* @return {string[]}*/
var letterCombinations = function(digits) {//直接用for循环,那3个数,4个数嘞?回溯!!!//字母映射:用数组就行呀!!!let letterMap=["","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"];//确定回溯参数//还是用数组,好回溯,知识结果最后进行一下处理就行let result=[],path=[];let length=digits.length;if(length===0)return result;//字符串->字符数组(split)if(length===1)return letterMap[digits].split("");let backtracking=(_digits,_length,_diIndex)=>{if(path.length===_length){result.push(path.join(""));return;}//多个集合中进行递归与回溯!//集合->letterMap[digits[_diIndex]]for(const v of letterMap[digits[_diIndex]]){//从一个集合中加入一个字符path.push(v);//递归,索引控制向下一个集合遍历backtracking(_digits,_length,_diIndex+1)//回溯path.pop();}}backtracking(digits,length,0);return result;
};

4.
在这里插入图片描述
————————————————————————————————

核心:
1.集合中元素可以重复使用
2.简枝操作,当sum+item>target时就break!if(sum+item>target)break;
3.可重复: backtracking(i,sum,target);
在这里插入图片描述

/*** @param {number[]} candidates* @param {number} target* @return {number[][]}*/
var combinationSum = function(candidates, target) {//允许相同的,不应该更好,不考虑剪枝的就是直接多层for//参数与返回值candidates.sort((a,b)=>a-b); // 排序let res=[],path=[];let backtracking=(index,sum,target)=>{//终止条件if(sum>target)return;if(sum===target){res.push(path.slice());return;}for(let i=index;i<candidates.length;i++){let item=candidates[i];//剪枝 sum>target,相加大于无需再递归if(sum+item>target)break;sum+=item;path.push(item);//递归,//需考虑 [2,2,3],[2,3,2],[3,2,2]情况backtracking(i,sum,target);//回溯path.pop();sum-=item;}}backtracking(0,0,target);return res;};

5.
在这里插入图片描述
————————————————————————————————

核心:
1.数组中包括相同元素,去重操作
2.去重先序排序 candidates.sort((a,b)=>a-b);
3.去重操作,与三数之和去重操作类似 if(j>i&&candidates[j]===candidates[j-1]){continue; //若当前元素和前一个元素相同 }

/*** @param {number[]} candidates* @param {number} target* @return {number[][]}*/
var combinationSum2 = function(candidates, target) {//核心:数组中包括相同元素,去重操作!三数求和当时也需考虑去重操作//参数和返回值let res=[],path=[],len=candidates.length;//!!!排序,去重时需要candidates.sort((a,b)=>a-b);let backtracking=(sum,i)=>{if(sum===target){res.push(path.slice());return;}for(let j=i;j<len;j++){const n=candidates[j];//!!!去重if(j>i&&candidates[j]===candidates[j-1]){//若当前元素和前一个元素相同//去重continue;}//剪枝if(sum+n>target)break;path.push(n);sum+=n;//递归backtracking(sum,j+1);//回溯path.pop();sum-=n;}}backtracking(0,0);return res;   
};

Further:组合问题概述

组合问题是经典的算法问题,通常涉及从一组元素中选择若干个元素,按照不同的规则生成所有符合条件的组合。根据问题的要求,组合问题可以按照不同的条件和约束进行分类。下面是一些常见的组合问题类型及其简要概述:

1. 组合的基本类型

这些问题通常要求从给定的一组元素中选择若干个元素,且不考虑顺序。

1.1. 组合总和问题(Combination Sum)
  • 描述:给定一个候选数字的集合和一个目标值,找到所有可以组合出目标值的数字组合。每个数字可以被无限次使用。
  • 典型问题
    • 组合总和(combinationSum):找到和为目标值的组合。
    • 组合总和 II(combinationSum2):与 combinationSum 类似,但数组中的元素是唯一的,不能重复选择。
1.2. 组合问题(Combinations)
  • 描述:从 n 个不同的元素中选择 k 个元素,返回所有可能的组合。选择时不考虑顺序。

  • 典型问题

    • n 个元素中选择 k 个元素的组合。
    // 示例:从 [1, 2, 3] 中选择 2 个元素
    combinations([1, 2, 3], 2);  // 结果:[ [1, 2], [1, 3], [2, 3] ]
    
1.3. 子集问题(Subsets)
  • 描述:从一组元素中找出所有的子集(包括空集)。该问题要求列出集合的所有组合,通常包括选择与不选择每个元素的情况。

  • 典型问题

    • 子集问题(subsets):给定一个整数数组,返回所有可能的子集。
    • 子集 II(subsetsWithDup):与 subsets 类似,但允许输入数组有重复元素。
    // 示例:给定 [1, 2, 3],输出所有子集
    subsets([1, 2, 3]);  // 结果:[ [], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3] ]
    

2. 带有额外约束的组合问题

这些问题通常包含额外的约束条件,如目标值、元素数量限制等。

2.1. 组合总和问题 II(Combination Sum II)
  • 描述:类似于组合总和问题(Combination Sum),但是输入数组中有重复元素,且每个数字只能使用一次。
  • 典型问题
    • 组合总和 II(combinationSum2):从一个包含重复数字的数组中,找出所有和为目标值的组合,每个数字只能用一次。
2.2. 组合求和问题(Combination Sum IV)
  • 描述:给定一个整数数组 nums 和目标整数 target,返回能够组合成目标值 target 的组合数。
  • 典型问题
    • 给定数组 nums = [1, 2, 3] 和目标 target = 4,返回能组成 target 的组合数(例如:[1, 1, 1, 1], [1, 3], [2, 2])。
2.3. 组合问题与选择的顺序有关(Permutations)
  • 描述:与组合不同,排列问题不仅考虑元素的选择,还要考虑元素的顺序。
  • 典型问题
    • 排列问题(permutations):从给定的数字中生成所有可能的排列。
    • 带重复元素的排列问题(permuteUnique):如果给定的数组包含重复元素,要求去除重复的排列。

3. 与排列、分配相关的组合问题

这类问题不仅仅关注组合,还涉及到排列或者将组合元素分配到不同的槽或组中。

3.1. 整数划分问题(Integer Partition)
  • 描述:将一个正整数分解为一组和为目标的正整数,可以允许元素重复。
  • 典型问题
    • 给定一个整数 n,将其分解为若干个正整数的和,可以多次使用同一个数字。
3.2. 组合分组问题(Combination Partition)
  • 描述:将一组数字分成若干个组合,每个组合的和为目标值。
  • 典型问题
    • 给定一个数组和目标值,将数组分成若干个子数组,使得每个子数组的和为目标值。
    • 例如,[1, 2, 3, 4],目标和为 5,应该如何划分出和为 5 的组合。

4. 与图相关的组合问题

这类问题涉及图结构,其中节点可以代表元素,边代表元素之间的关系,解空间的搜索通常采用深度优先搜索(DFS)或广度优先搜索(BFS)方法。

4.1. 图的遍历问题(Graph Traversal)
  • 描述:例如,通过图的回溯算法遍历图的节点以找到所有可能的组合。
  • 典型问题
    • 通过图的遍历找出从一个节点到另一个节点的所有路径。
    • 例如,找出所有从节点 A 到节点 B 的路径。

5. 动态规划与回溯结合的组合问题

这类问题结合了动态规划和回溯算法,通常用于处理大规模数据或优化问题。

5.1. 背包问题(Knapsack)
  • 描述:给定一组物品,每个物品有重量和价值,背包有最大承重,求最大价值的组合。
  • 典型问题
    • 01背包:每个物品只能选择一次,求能获得的最大价值。
    • 完全背包:每个物品可以选择多次,求最大价值。
5.2. 分割问题(Partition Problem)
  • 描述:给定一个整数数组,判断是否可以将其分割成两个子集,使得两个子集的和相等。
  • 典型问题
    • 子集和问题:判断给定数组是否可以分成两个和相等的子集。

6. 其他变种组合问题

还有一些组合问题可能带有更为复杂的条件或要求,比如:

6.1. 组合最大化问题
  • 描述:给定一个数组,选择若干个元素,使得它们的和尽量接近某个目标,或者在某些约束条件下求最大值。
6.2. 最大子集和问题
  • 描述:从给定的数组中选出若干个子集,使得它们的和最大,通常会使用动态规划进行优化。

总结:

组合问题的分类方法有很多,通常可以根据是否允许重复选择、是否考虑顺序、是否存在约束条件等多个方面进行划分。常见的组合问题包括:基础的子集与组合问题、带有约束的组合问题(如组合总和、分割问题等)、与排列、分配相关的问题(如背包问题、整数划分问题等)以及需要结合动态规划的复杂组合问题等。在处理这些问题时,回溯算法常常被用于解决那些穷举解空间的问题,而动态规划则适用于那些有子结构且可以优化的问题。


http://www.mrgr.cn/news/82305.html

相关文章:

  • jenkins入门4 --window执行execute shell
  • uniapp实现后端数据i18n国际化
  • 深入理解 Java 接口的回调机制
  • 如何在6种有用的方法中将照片从Android转移到笔记本电脑
  • Redis四种模式在Spring Boot框架下的配置
  • Excel重新踩坑5:二级下拉列表制作;★数据透视表;
  • 25年1月更新。Windows 上搭建 Python 开发环境:Python + PyCharm 安装全攻略(文中有安装包不用官网下载)
  • 用Tkinter制作一个用于合并PDF文件的小程序
  • linux安装git
  • 【Rust自学】9.4. 什么时候该使用panic!
  • 【Rust自学】9.3. Result枚举与可恢复的错误 Pt.2:传播错误、?运算符与链式调用
  • LeetCode算法题——螺旋矩阵ll
  • Prometheus之终极指南(The Ultimate Guide to Prometheus)
  • 题解:监控屏幕调整问题
  • UE蓝图战利品掉落动画
  • EFEVD: Enhanced Feature Extraction for Smart Contract Vulnerability Detection
  • 蓝桥杯JAVA--002
  • 基于深度学习的视觉检测小项目(五) 项目真正的开端
  • 前端如何用 canvas 做电影院选票功能
  • UE5动画蓝图
  • 24.Java 新特性扩展(重复注解、类型注解)
  • 人工智能安全与隐私——联邦遗忘学习(Federated Unlearning)
  • 51c视觉~合集40
  • 硬件设计-关于ADS54J60的校准问题
  • 多种方式访问mysql的对比分析
  • Pygame Zero(pgzrun)详解(简介、使用方法、坐标系、目录结构、语法参数、安装、实例解释)