忍者算法

Appearance

90%面试者都漏掉的细节！用「购物车理论」秒懂组合总和问题 ​

大家好，我是忍者算法。今天要挑战的这道题，表面是数字组合游戏，实则暗藏回溯算法的精髓。据说90%的面试者都会忽视关键细节，让我们用5分钟彻底攻克LeetCode 39题「组合总和」！

🛒 一个真实的生活场景 ​

小明在超市凑满减活动，手握100元优惠券发愁：

  • "巧克力20元，薯片15元，可乐5元..."
  • "同一商品可以拿多件"
  • "怎样才能刚好凑满100元的所有组合？"

这场景竟与算法题完美对应！让我们揭开题目的真面目。

💡 算法题解析 ​

题目要求：
给定无重复元素的数组和一个目标数，找出所有唯一组合，满足：

  • 组合中数字和等于目标
  • 同一数字可无限次使用
  • 解集不能有重复组合（如[2,2,3]和[3,2,2]视为同一组合）

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

😱 新手易踩的三个坑 ​

  1. 暴力枚举：直接遍历所有子集，产生大量重复组合（时间复杂度O(2^n)）
  2. 遗漏剪枝：不排序直接处理，无法提前终止无效搜索
  3. 路径回溯：忘记移除已添加元素，导致结果串扰

就像在超市盲目拿商品，既浪费时间又容易拿错！

🚀 高手的解题秘籍 ​

核心思路：回溯算法 + 剪枝优化 ​

java
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(candidates); // 关键第一步：排序为剪枝做准备
    backtrack(result, new ArrayList<>(), candidates, target, 0);
    return result;
}

private void backtrack(List<List<Integer>> result, List<Integer> path, 
                      int[] candidates, int remain, int start) {
    if (remain < 0) return; // 超额直接返回
    if (remain == 0) {      // 找到合法组合
        result.add(new ArrayList<>(path));
        return;
    }
    
    for (int i = start; i < candidates.length; i++) {
        if (candidates[i] > remain) break; // 剪枝：提前终止无效分支
        
        path.add(candidates[i]);           // 选择当前元素
        backtrack(result, path, candidates, remain - candidates[i], i); // 关键：允许重复选择
        path.remove(path.size() - 1);      // 撤销选择（回溯）
    }
}

算法图解 ​

  1. 排序数组：[2,3,5] → [2,3,5]（为剪枝铺垫）
  2. 构建决策树：每个节点代表选择某个元素
  3. 剪枝策略：当累计值超过target时停止向下搜索
  4. 路径记录：用List保存当前选择路径

就像在超市：

  • 先按价格排序商品（排序）
  • 从便宜的开始拿（剪枝）
  • 记录已选商品（路径）
  • 凑满金额立即结算（终止条件）

🏆 复杂度优化关键 ​

  1. 排序剪枝：时间复杂度从O(2^n)降到O(n^(target/min))
  2. 避免重复：通过start参数控制选择范围，保证组合唯一性
  3. 空间优化：复用path列表，空间复杂度O(target/min)

💼 面试灵魂三问 ​

  1. 为什么需要排序？

    • 实现剪枝优化，提前终止无效搜索路径
    • 保证组合元素的递增顺序，避免重复组合

  2. 如何处理元素重复使用？

    • 递归时传递start=i而非i+1，允许重复选择当前元素

  3. 算法适用哪些变种题？

    • 组合总和II（不可重复使用元素）
    • 电话号码字母组合
    • 全排列问题

📌 核心技巧总结 ​

掌握回溯三板斧：

  1. 选择：记录当前决策
  2. 约束：通过剪枝减少搜索
  3. 撤销：回溯到上一步状态

作者：忍者算法
公众号：忍者算法

🎁 回复【刷题清单】获取LeetCode高频面试题合集
🧑‍💻 回复【代码】获取多语言完整题解
💡 回复【加群】加入算法交流群，一起进步

#算法面试 #LeetCode #回溯算法 #编程思维