【每日算法】LeetCode 39. 组合总和

对前端开发者而言，学习算法绝非为了“炫技”。它是你从“页面构建者”迈向“复杂系统设计者”的关键阶梯。它将你的编码能力从“实现功能”提升到“设计优雅、高效解决方案”的层面。从现在开始，每天投入一小段时间，结合前端场景去理解和练习，你将会感受到自身技术视野和问题解决能力的质的飞跃。------ 算法：资深前端开发者的进阶引擎

LeetCode 39. 组合总和 —— 从前端视角深入理解回溯算法

1. 题目描述

给你一个无重复元素的整数数组candidates和一个目标整数target，找出candidates中可以使数字和为目标数target的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。

candidates中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

示例 1：

输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]] 解释： 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选， 7 = 7 。 仅有这两种组合。

示例 2：

输入：candidates = [2,3,5], target = 8 输出：[[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入：candidates = [2], target = 1 输出：[]

2. 问题分析

这是一个典型的组合搜索问题，需要从候选数组中找出所有满足条件的组合。问题的核心特点包括：

1. 元素可重复使用：同一个数字可以被无限次选取
2. 组合而非排列：[2,2,3]和[2,3,2]被视为相同组合
3. 结果需要去重：不能出现重复的组合

从前端开发的角度看，这类问题类似于：

• UI组件的动态渲染：根据不同的条件组合渲染不同的组件
• 路由权限配置：根据用户权限组合出可访问的路由列表
• 表单验证规则组合：根据不同的业务规则组合出验证逻辑

3. 解题思路

3.1 核心思路：回溯算法（DFS）

回溯算法是解决这类组合搜索问题的标准解法。其核心思想是：

1. 通过深度优先搜索（DFS）遍历所有可能的组合
2. 在搜索过程中维护当前路径（已选择的数字列表）和当前和
3. 当当前和等于目标值时，保存当前路径
4. 当当前和超过目标值时，停止继续搜索（剪枝）
5. 通过控制搜索起始位置避免重复组合

3.2 算法步骤详解

// 伪代码流程functioncombinationSum(candidates,target){1.对 candidates 进行排序（优化剪枝）2.定义结果数组 result=[]3.定义回溯函数backtrack(start,currentCombination,currentSum):a.如果 currentSum===target:将 currentCombination 加入 result，返回 b.如果 currentSum>target:直接返回（剪枝） c.从 start 开始遍历 candidates:-选择当前数字 candidates[i]-更新 currentCombination 和 currentSum-递归调用backtrack(i,...)// 注意：这里是 i，不是 i+1，因为可以重复使用-撤销选择（回溯）4.调用backtrack(0,[],0)5.返回 result

3.3 复杂度分析

时间复杂度：O(N^(T/M))，其中 N 是候选数组长度，T 是目标值，M 是候选数组中的最小值

• 这是回溯算法的典型时间复杂度，实际运行中通过剪枝会好很多
• 最坏情况下需要探索所有可能的组合

空间复杂度：O(T/M)

• 递归调用栈的深度，最多不会超过目标值除以最小候选值的商

4. 代码实现

4.1 标准回溯实现（最优解）

/** * @param {number[]} candidates * @param {number} target * @return {number[][]} */varcombinationSum=function(candidates,target){constresult=[];// 排序以便剪枝优化candidates.sort((a,b)=>a-b);/** * 回溯函数 * @param {number} start - 当前搜索起始位置 * @param {number[]} path - 当前组合路径 * @param {number} sum - 当前路径的数字和 */constbacktrack=(start,path,sum)=>{// 找到满足条件的组合if(sum===target){result.push([...path]);// 深拷贝当前路径return;}// 遍历候选数字for(leti=start;i<candidates.length;i++){constnum=candidates[i];constnewSum=sum+num;// 剪枝：如果当前和已经超过目标值，由于数组已排序，后续数字只会更大if(newSum>target){break;}// 选择当前数字path.push(num);// 递归搜索：注意这里传入 i 而不是 i+1，因为可以重复使用backtrack(i,path,newSum);// 撤销选择（回溯）path.pop();}};// 从第 0 个位置开始搜索backtrack(0,[],0);returnresult;};

4.2 动态规划解法（思路扩展）

虽然回溯是本题的最优解，但了解动态规划思路有助于拓展思维：

varcombinationSumDP=function(candidates,target){// dp[i] 表示目标值为 i 的所有组合constdp=newArray(target+1).fill().map(()=>[]);// 目标值为 0 时，只有一种组合：空数组dp[0]=[[]];// 遍历每个候选数字for(constnumofcandidates){// 从 num 开始更新到 targetfor(leti=num;i<=target;i++){// 对于 dp[i - num] 中的每个组合for(constcombinationofdp[i-num]){// 将当前数字加入组合，形成新的组合dp[i].push([...combination,num]);}}}returndp[target];};

注意：动态规划解法在本题中空间复杂度较高，且难以直接处理去重问题（需要额外处理），不如回溯算法直观高效。

5. 各实现思路对比

实现方式	时间复杂度	空间复杂度	优点	缺点	适用场景
标准回溯	O(N^(T/M))	O(T/M)	1. 思路清晰直观 2. 天然处理去重问题 3. 剪枝后效率较高	1. 递归深度可能较大 2. 需要手动维护状态	大多数组合搜索问题，特别是需要所有解的
动态规划	O(N * T * K) (K为平均组合数)	O(T * K)	1. 自底向上构建 2. 适合只需要计数的情况	1. 空间占用大 2. 组合去重复杂 3. 需要存储所有中间结果	只需要解的数量或特定值的解

6. 总结

6.1 核心要点回顾

1. 回溯算法是解决组合搜索问题的利器，通过"选择-探索-撤销"的模式遍历所有可能解
2. 排序剪枝能显著提升算法效率，提前排除不可能的分支
3. 避免重复组合的关键是控制搜索起始位置，而不是简单的去重

6.2 前端实际应用场景

1. 动态表单生成：

   // 根据用户选择的组件类型，组合出不同的表单配置// 类似组合总和，从组件库中选取组件组合成目标表单

2. 路由权限组合：

   // 用户有多种权限，需要组合出所有可访问的路由// 权限可以重复使用（多个路由需要相同权限）

3. 商品规格组合：

   // 电商平台中，商品有多个属性（颜色、尺寸等）// 需要组合出所有可能的SKU，并检查库存

4. 组件组合渲染：

   // 根据页面配置，从组件池中选取组件组合渲染// 类似组合总和，找出所有满足页面布局的组件组合