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

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

article 2025/1/4 18:06:45

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

回溯

回溯模板

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)+1
        for(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.kler.cn/a/464670.html

相关文章：

  • 32单片机从入门到精通之软件编程——中断处理(九)
  • stm32入门元件介绍
  • 【NX入门篇】
  • UE5失真材质
  • 5大常见高并发限流算法选型浅析
  • AI数据标注师理论部分考试题库 - 500题
  • Oracle 使用 sql profile 固定执行计划
  • 国产编辑器EverEdit - 常用资源汇总
  • QT---------自定义插件和库
  • Unity3D Huatuo：零成本高性能的全平台原生C#热更新方案详解
  • 玩《燕云十六声》时游戏文件丢失怎么办？
  • RabbitMQ基础篇之Java客户端 Topic交换机
  • 基于VSCode软件框架的RISC-V IDE MRS2正式上线发布
  • 使用Pandoc复制ChatGPT生成的高数公式文本
  • 学习笔记078——Java Properties类使用详解
  • js按日期按数量进行倒序排序,然后再新增一个字段,给这个字段赋值 10 到1
  • Lua迭代器如何使用？
  • element ui 组件 时间选择器出现转换问题的解决办法
  • 【门铃工作原理】2021-12-25
  • scipy和statsmodels之Python实现
  • Unity网络通信相关
  • 算命网站源码PHP框架_附2025新版设计书教程
  • Linux系统编程：深入理解计算机软硬件体系和架构
  • 前端页面上传文件：解决 ERR_UPLOAD_FILE_CHANGED
  • 基于Python flask 的微博高校舆情分析系统，高校微博情感分析大屏可视化
  • sql优化（1）