Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
- All numbers (including target) will be positive integers.
- Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
- The solution set must not contain duplicate combinations.
For example, given candidate set 10,1,2,7,6,1,5
and target 8
,
A solution set is: [1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]
Solution:
注意先排序,保证从小到大。递归终止的条件是:
- target值小于0,说明后面不可能有解了。
- target值等于0,说明已经找到解。
public List<List<Integer>> combinationSum2(int[] num, int target) { List<List<Integer>> result = new ArrayList<>(); Arrays.sort(num); combine(result, new ArrayList<Integer>(), num, target, 0); return result; } private void combine(List<List<Integer>> result, List<Integer> list, int[] num, int target, int pos) { if(target < 0) return; if(target == 0) { result.add(new ArrayList<Integer>(list)); return; } for(int i=pos; i<num.length; i++) { if(i>pos && num[i] == num[i-1]) continue; list.add(num[i]); combine(result, list, num, target-num[i], i+1); list.remove(list.size()-1); } }
相关推荐
c语言入门 C语言_leetcode题解之40-combination-sum-ii.c
js js_leetcode题解之40-combination-sum-II.js
java java_leetcode题解之Combination Sum II.java
java java_leetcode题解之Combination Sum.java
java java_leetcode题解之Combination Sum IV.java
c语言入门 C语言_leetcode题解之39-combination-sum.c
js js_leetcode题解之39-combination-sum.js
java java_leetcode题解之Combination Sum III.java
java入门 java_leetcode题解之039_Combination_Sum
python python_leetcode题解之216_Combination_Sum_III.py
combination sum: 39, 40, 216 - palindrome partitioning - regex - sudoku solver: 37 排序 - merge sort - quick sort - insertion sort - selection sort - counting sort 位操作 - find the only element which...
9. **模拟和回溯**:对于某些组合优化问题,可以使用回溯法来枚举所有可能的解决方案,例如"组合总和"(Combination Sum)。 10. **排序与堆**:数组的排序问题可以通过快速排序、归并排序等经典算法解决,而"最大...
第 296 章PY 和 GO 中的 Leetcode 我在 Python Golang ...Leetcode ...40:combination-sum-ii:传递最后选择的索引 41:先缺失正,交换 42:只是提醒:块 - 垃圾箱 43:多字符串,i+j,i+j+1 44:通配符
leetcode怎么销号 LeetCode-Solutions :green_heart:My own LeetCode solutions No. Problem LeetCode 力扣 Python Go Solution Difficulty Tag 0017 Letter Combinations of a Phone Number Medium 回溯、暴力 0034...
- Combination Sum: 找出所有相加之和为特定值的组合。 - First Missing Positive: 找出数组中缺失的最小正数。 - Trapping Rain Water: 给定一个数组,其中每个元素代表一个宽度为1的柱子高度,计算能接多少雨水。 ...
leetcode怎么计算空间复杂度是指 LeetCode-Solution my first solution of LeetCode 2015-5-7 Problem 95,98(80 already!) 我经常在递归的结束地方忘记return!!! 题型一:经典暴力递归:(里面涉及到重复不重复的...
leetcode题库 Little Algorithm 从 2020 年初开始,我在公众号《面向大象编程》上发表面试算法、LeetCode 题解相关文章,至今收获不少好评。此仓库是公众号内容的补充,包括公众号文章涉及到的题目的参考代码,以及 ...
1. 回溯法:中等难度题目中,回溯法是一种常见的解决方案,如"Combination Sum"(组合总和)和"N-Queens"(皇后问题),通过回溯可以找到所有可能的解。 2. 动态规划:"House Robber"(打家劫舍)系列问题,展示了...