39. 组合总和

39. 组合总和

实现

class Solution { public List> combinationSum(int[] candidates, int target) { int len = candidates.length; List> res = new ArrayList<>(); if (len == 0) { return res; } Deque path = new ArrayDeque<>(); dfs(candidates, 0, len, target, path, res); return res; } /** * @param candidates 候选数组 * @param begin 搜索起点 * @param len 冗余变量，是 candidates 里的属性，可以不传 * @param target 每减去一个元素，目标值变小 * @param path 从根结点到叶子结点的路径，是一个栈 * @param res 结果集列表 */ private void dfs(int[] candidates, int begin, int len, int target, Deque path, List> res) { // target 为负数和 0 的时候不再产生新的孩子结点 if (target < 0) { return; } if (target == 0) { res.add(new ArrayList<>(path)); return; } // 重点理解这里从 begin 开始搜索的语意 for (int i = begin; i < len; i++) { path.addLast(candidates[i]); // 注意：由于每一个元素可以重复使用，下一轮搜索的起点依然是 i，这里非常容易弄错 dfs(candidates, i, len, target - candidates[i], path, res); // 状态重置 path.removeLast(); } }}

​​看大佬题解​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。