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：回溯算法

算法思路

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

JavaScript实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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（不能重复使用元素）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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，不重复使用）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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;
}

关键点解析

  1. 回溯模板：

    • 做出选择（path.push）
    • 递归探索
    • 撤销选择（path.pop）

  2. 剪枝优化：

    • 排序后可以提前终止不可能的分支
    • 跳过重复组合（在变体II中很重要）

  3. 避免重复：

    • 通过控制start索引确保组合唯一性
    • 不使用之前已经用过的元素（除非允许重复使用）

实际应用场景

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

调试技巧

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

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

解决方案2：DFS

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

代码结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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
};

变量说明

  1. ans: 存储所有符合条件的组合结果

  2. dfs函数参数:

    • target: 剩余需要凑足的目标值
    • combine: 当前已选择的数字组合
    • i: 当前考虑的数字在candidates中的索引

算法流程解析

1. 基本情况处理

1
2
3
if (i === candidates.length) {
    return
}
  • 作用：当已经考虑完所有候选数字时，结束当前递归分支
  • 意义：防止数组越界访问

2. 找到有效组合

1
2
3
4
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不变（允许重复使用同一数字）

  • 意义：探索包含当前数字的所有可能性