2025-06-16

algorithms►leetcode

011-组合总和（深度优先搜索（DFS））

组合总和问题（深度优先搜索（DFS））

问题描述

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

示例

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3], [7]]
解释：
2+2+3 = 7
7 = 7

解决方案1：回溯算法

算法思路

排序数组（可选，但有助于剪枝优化）
回溯遍历：
- 从当前位置开始尝试选择数字
- 如果选择当前数字后总和小于target，继续递归
- 如果等于target，保存结果
- 如果超过target，停止向下搜索（剪枝）
避免重复组合：通过控制遍历起始位置

JavaScript实现

function combinationSum(candidates, target) {
    const result = [];
    
    // 排序有助于剪枝
    candidates.sort((a, b) => a - b);
    
    function backtrack(start, path, remaining) {
        if (remaining === 0) {
            result.push([...path]);
            return;
        }
        
        for (let i = start; i < candidates.length; i++) {
            // 剪枝：如果当前数字已经大于剩余值，后面的更大，直接跳过
            if (candidates[i] > remaining) break;
            
            path.push(candidates[i]);
            backtrack(i, path, remaining - candidates[i]);
            path.pop(); // 回溯
        }
    }
    
    backtrack(0, [], target);
    return result;
}

复杂度分析

时间复杂度：O(N^(T/M + 1))，其中N是候选数数量，T是目标值，M是最小候选数
空间复杂度：O(T/M)（递归栈深度）

变体问题

变体1：组合总和II（不能重复使用元素）

function combinationSum2(candidates, target) {
    const result = [];
    candidates.sort((a, b) => a - b);
    
    function backtrack(start, path, remaining) {
        if (remaining === 0) {
            result.push([...path]);
            return;
        }
        
        for (let i = start; i < candidates.length; i++) {
            // 跳过重复元素
            if (i > start && candidates[i] === candidates[i-1]) continue;
            if (candidates[i] > remaining) break;
            
            path.push(candidates[i]);
            backtrack(i + 1, path, remaining - candidates[i]); // i+1表示不能重复使用
            path.pop();
        }
    }
    
    backtrack(0, [], target);
    return result;
}

变体2：组合总和III（限制组合长度）

找出所有k个数的组合，使其和等于n（数字仅限1-9，不重复使用）

function combinationSum3(k, n) {
    const result = [];
    
    function backtrack(start, path, remaining) {
        if (path.length === k && remaining === 0) {
            result.push([...path]);
            return;
        }
        
        for (let i = start; i <= 9; i++) {
            if (i > remaining) break;
            path.push(i);
            backtrack(i + 1, path, remaining - i);
            path.pop();
        }
    }
    
    backtrack(1, [], n);
    return result;
}

关键点解析

回溯模板：
- 做出选择（path.push）
- 递归探索
- 撤销选择（path.pop）
剪枝优化：
- 排序后可以提前终止不可能的分支
- 跳过重复组合（在变体II中很重要）
避免重复：
- 通过控制start索引确保组合唯一性
- 不使用之前已经用过的元素（除非允许重复使用）

实际应用场景

商品组合优惠计算
资源分配问题
密码破解尝试
游戏中的道具合成系统

调试技巧

可以在回溯函数中加入日志，观察搜索过程：

function backtrack(start, path, remaining) {
    console.log(`start=${start}, path=[${path}], remaining=${remaining}`);
    // ...其余代码...
}

解决方案2：DFS

这段代码使用深度优先搜索（DFS）来解决组合总和问题。下面我将逐部分详细解析这段代码的工作原理。

代码结构

var combinationSum = function(candidates, target) {
    const ans = []
    function dfs(target, combine, i) {
        if (i === candidates.length) {
            return
        }
        if (target === 0) {
            ans.push(combine)
            return
        }
        dfs(target, combine, i+1)
        if (target - candidates[i] >= 0) {
            dfs(target-candidates[i],[...combine, candidates[i]] , i)
        }
    }
    dfs(target, [], 0)
    return ans
};

变量说明

ans: 存储所有符合条件的组合结果
dfs函数参数:
- target: 剩余需要凑足的目标值
- combine: 当前已选择的数字组合
- i: 当前考虑的数字在candidates中的索引

算法流程解析

1. 基本情况处理

1
2
3

if (i === candidates.length) {
    return
}

作用：当已经考虑完所有候选数字时，结束当前递归分支
意义：防止数组越界访问

2. 找到有效组合

if (target === 0) {
    ans.push(combine)
    return
}

作用：当target减到0时，表示当前组合满足条件
细节：将当前组合combine加入结果集ans中
注意：这里直接保存了combine的引用，在JavaScript中由于数组是对象，可能会导致问题（改进方法见后文）

3. 不选择当前数字

1	dfs(target, combine, i+1)

作用：跳过当前数字，直接考虑下一个数字
意义：探索不包含当前数字的所有可能性
执行路径：保持target不变，组合不变，索引+1

4. 选择当前数字

1
2
3

if (target - candidates[i] >= 0) {
    dfs(target-candidates[i],[...combine, candidates[i]] , i)
}

条件判断：只有当前数字不大于剩余target时才考虑选择它
操作：
- 从target中减去当前数字的值
- 将当前数字加入组合（使用扩展运算符...创建新数组）
- 保持索引i不变（允许重复使用同一数字）
意义：探索包含当前数字的所有可能性

2025-06-16

algorithms►leetcode

012-跳跃游戏能否到终点+最小跳跃次数（贪心算法）

跳跃游戏问题（图文解析）

跳跃游戏 I（能否到达终点）

问题描述

给定一个非负整数数组 nums，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。

示例

输入：nums = [2,3,1,1,4]
输出：true
解释：从位置 0 跳到位置 1，再从位置 1 跳到位置 4。

解题思路：贪心算法

维护一个变量 maxReach 表示当前能到达的最远位置
遍历数组，更新 maxReach
如果当前位置超过了 maxReach，说明无法继续前进
如果 maxReach 能覆盖最后一个位置，返回 true

JavaScript实现

function canJump(nums) {
    //maxReach表示能到达的最大索引位置
    let maxReach = 0;
    for (let i = 0; i < nums.length; i++) {
        if (i > maxReach) return false;
        maxReach = Math.max(maxReach, i + nums[i]);
        if (maxReach >= nums.length - 1) return true;
    }
    return true;
}

图示说明（nums = [2,3,1,1,4]）

位置: 0(2) → 1(3) → 2(1) → 3(1) → 4(4)
步骤:
1. i=0: maxReach = max(0, 0+2) = 2
   [可以覆盖位置1,2]
   
2. i=1: 1 <= 2 (可以到达)
   maxReach = max(2, 1+3) = 4
   [可以覆盖位置4，直接返回true]

跳跃游戏 II（最少跳跃次数）

问题描述

在保证能到达终点的前提下，找出最少的跳跃次数。

示例

输入：nums = [2,3,1,1,4]
输出：2
解释：最少需要跳2次：0 → 1 → 4。

解题思路：贪心算法优化

维护三个变量：
- maxReach：当前能到达的最远位置
- steps：当前步数能到达的边界
- jumps：跳跃次数
遍历数组：
- 更新 maxReach
- 到达边界时增加跳跃次数，并更新边界

JavaScript实现

function jump(nums) {
    let jumps = 0, maxReach = 0, steps = 0;
    for (let i = 0; i < nums.length - 1; i++) {
        maxReach = Math.max(maxReach, i + nums[i]);
        if (i === steps) {
            jumps++;
            steps = maxReach;
        }
    }
    return jumps;
}

图示说明（nums = [2,3,1,1,4]）

位置: 0(2) → 1(3) → 2(1) → 3(1) → 4(4)
步骤:
1. i=0:
   - maxReach = max(0, 0+2) = 2
   - steps=0 (到达边界)
   - jumps=1, steps更新为2
   [第1跳可以到达位置1,2]

2. i=1:
   - maxReach = max(2, 1+3) = 4
   - i ≠ steps (1≠2)
   
3. i=2:
   - maxReach保持4
   - i=steps=2 (到达边界)
   - jumps=2, steps更新为4
   [第2跳可以到达位置4]
   
4. 结束，总共跳了2次

关键点总结

贪心选择：每次选择能跳得最远的位置
跳跃游戏I：
- 时间复杂度：O(n)
- 空间复杂度：O(1)
- 只需判断能否到达终点
跳跃游戏II：
- 时间复杂度：O(n)
- 空间复杂度：O(1)
- 需要计算最少跳跃次数
- 注意遍历到 nums.length - 1 即可
边界情况：
- 空数组或单元素数组
- 包含0的情况（如 [3,2,1,0,4]）

常见误区

认为必须按最大步数跳跃（实际上可以跳1~最大步数的任意值）
在跳跃游戏II中使用BFS导致效率低下
忽略数组包含0的情况处理

复杂度对比

算法	时间复杂度	空间复杂度
动态规划	O(n²)	O(n)
贪心算法	O(n)	O(1)

贪心算法是这类问题的最优解。