摘要：题目给定一个数组和一个目标数，找出中所有可以使数字和为的组合。中的每个数字在每个组合中只能使用一次。注意解集不能包含重复的组合。示例输入输出示例输入输出提示答案回溯法排序后去重
题目：
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
注意：解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[ [1,1,6], [1,2,5], [1,7], [2,6]]示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[ [1,2,2], [5]]提示:
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30
答案：
class Solution { List<List<Integer>> lists; public List<List<Integer>> combinationSum2(int[] candidates, int target) { //回溯法,排序后去重 Arrays.sort(candidates); lists = new ArrayList<>(); List<Integer> list = new ArrayList<>(); backTrace(list, candidates, target, 0); return lists; } public void backTrace(List<Integer> list, int[] candidates, int target, int index){ if(target == 0){ lists.add(new ArrayList<>(list)); return; } if(index >= candidates.length) return; if(target < 0 && candidates[index] > 0) return; for(int i = index; i < candidates.length; i++){ list.add(candidates[i]); backTrace(list, candidates, target - candidates[i], i + 1); while (i < candidates.length - 1 && candidates[i] == candidates[i + 1]) { i++; } list.remove(list.size() - 1); } }}文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/123184.html
摘要：算法前端发展的再快，也不要忘记精进自己的算法，算法是灵魂和核心。我会把我刷过的算法题总结归类，不断完善。 算法 前端发展的再快，也不要忘记精进自己的算法，算法是灵魂和核心。我会把我刷过的算法题总结归类，不断完善。欢迎大家关注。 数组和堆栈 数组去重 旋转数组 如何快速找出两个数之和等于某一个值的两个数？ 快排 排序算法大总结 快速找到数组中的最大值 多维数组的展开 二分查找 有效的括...
摘要：分布式的管理和当我在谈论架构时我在谈啥状态码详解无状态协议和请求支持哪些方法分层协议栈有哪些数据结构运用场景说说你常用的命令为什么要有包装类面向对象的特征是啥是啥有什么好处系统设计工程在线诊断系统设计与实现索引背后的数据结构及算法原理软技能 HTTP 【HTTP】分布式session的管理 【HTTP】Cookie和Session 【HTTP】当我在谈论RestFul架构时我在谈啥？...
摘要：计算从根到叶子节点生成的所有数字之和。说明叶子节点是指没有子节点的节点。代码方法二，自顶向下搜索深度优先搜索，搜索过程中维护一个当前累加值，一旦搜索到叶子节点，就将现在的当前累加值加入结果中。 题目地址：https://leetcode-cn.com/probl...题目描述： 给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。 例如，从...
摘要：图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。因此使用一个数组代表每个节点的入度，若入度为就是叶子节点。 题目地址：https://leetcode-cn.com/probl...题目描述： 对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小...
摘要：题目给定一个可包含重复数字的序列，按任意顺序返回所有不重复的全排列。示例输入输出示例输入输出提示答案回溯法使用数组判断是否访问过，排序后跳过与前一个相同的 题目： ...
阅读 2618·2021-11-12 10:36
阅读 2256·2021-08-23 09:47
阅读 1674·2019-08-30 15:44
阅读 1399·2019-08-30 14:10
阅读 2240·2019-08-29 16:52
阅读 2333·2019-08-29 16:40
阅读 1581·2019-08-29 16:17
阅读 2406·2019-08-26 13:21
