AlgoViz Lab交互式算法学习
Algorithms first

组合总和 · 交互式算法学习

找出可重复选择元素、总和为 target 的组合。

#39 · 回溯

组合总和

Combination Sum

测试用例candidates = [2,3,6,7], target = 7
递归树3 个关键状态
步骤 1选择 2，remain 变 5。path=[2]
2367
推荐

有序起点剪枝回溯

时间 指数级空间 O(target/min)

下一层只从当前下标继续选，避免排列重复；排序后可提前停止。

1function combinationSum(a, t) {2  a.sort((x, y) => x - y);3  const out = [];4 5  function dfs(start, remain, path) {6    if (remain === 0) {7      out.push([...path]);8      return9    }10    for (let i = start; i < a.length && a[i] <= remain; i++) {11      path.push(a[i]);12      dfs(i, remain - a[i], path);13      path.pop()14    }15  }16  dfs(0, t, []);17  return out;18}
多语言参考

Java · C++ · Go

来源 · CC BY-SA 4.0 ↗

这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。

1class Solution {2    private List<List<Integer>> ans = new ArrayList<>();3    private List<Integer> t = new ArrayList<>();4    private int[] candidates;5 6    public List<List<Integer>> combinationSum(int[] candidates, int target) {7        Arrays.sort(candidates);8        this.candidates = candidates;9        dfs(0, target);10        return ans;11    }12 13    private void dfs(int i, int s) {14        if (s == 0) {15            ans.add(new ArrayList(t));16            return;17        }18        if (s < candidates[i]) {19            return;20        }21        for (int j = i; j < candidates.length; ++j) {22            t.add(candidates[j]);23            dfs(j, s - candidates[j]);24            t.remove(t.size() - 1);25        }26    }27}
交互式算法学习

从执行步骤真正理解 LeetCode 经典 150

本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。

多形态可视化数组、矩阵、DP 表、递归树、树图、链表、栈队列堆、区间和状态机按解法选择。
动画与代码同步当前状态、步骤说明、变量和代码高亮保持一一对应，可逐步播放和回退。
适合面试复习每种方案都给出思路、时间复杂度、空间复杂度、测试用例和 LeetCode 中文原题入口。
AlgoViz Lab

组合总和 · 解法对比

AlgoViz Lab

找出可重复选择元素、总和为 target 的组合。

测试用例
candidates = [2,3,6,7], target = 7
题目分类
回溯
解法对比
2
方案 1

无序选择回溯 + 集合去重

每层尝试所有数字，命中后把排序组合放集合。

时间
指数级
空间
O(target)
方案 2

有序起点剪枝回溯

下一层只从当前下标继续选，避免排列重复；排序后可提前停止。

时间
指数级
空间
O(target/min)