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

Javascript算法——回溯算法（组合问题）

news 来源：原创 2025/7/13 8:12:51

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

回溯

回溯模板

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. 最大子集和问题

描述：从给定的数组中选出若干个子集，使得它们的和最大，通常会使用动态规划进行优化。

总结：

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

回溯