[分析] 输入数组中的每个元素至多使用一次,相较于Combination Sum,需要做两个小改动,改动虽小但很关键。改动1是在向下递归时传下去的start是下一个元素的下标,这保证每个元素至多只被使用一次。改动2是for循环体前面的if判断,这个判断的作用是避免出现重复结果,虽然每个元素不能被重复使用,但重复出现在结果中是允许的(考虑[1,1], 2),因此限定只对第一次得到某个数进行递归(i > start 而不是 i > 0, 条件设为 i > 0 会fail @[1,1],2),接下来就跳过这个数,因为在同一层递归中,for循环的每个元素在结果中处于相同位置,若不跳过则会出现重复结果,考虑[1,1,1],3 进行体会。
参考Code Canker的解析
http://blog.csdn.net/linhuanmars/article/details/20829099,并补充上自己的理解。
[url]
public class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
Arrays.sort(candidates);
recur(candidates, target, 0, new ArrayList<Integer>(), result);
return result;
}
public void recur(int[] candidates, int target, int start, ArrayList<Integer> oneAns, List<List<Integer>> result) {
if (target <= 0) {
if (target == 0)
result.add((ArrayList<Integer>) oneAns.clone());
return;
}
for (int i = start; i < candidates.length && candidates[i] <= target; i++) {
if (i > start && candidates[i] == candidates[i - 1])
continue;
oneAns.add(candidates[i]);
recur(candidates, target - candidates[i], i + 1, oneAns, result);
oneAns.remove(oneAns.size() - 1);
}
}
}
[/url]
分享到:
相关推荐
文件标题"C语言-leetcode题解之40-combination-sum-ii.c"暗示了本文的内容是围绕LeetCode上的第40题"Combination Sum II"编写的题解,并且使用C语言来实现解决方案。第40题是组合总和问题的一个变种,要求在一组数字...
首先,“js-leetcode题解之40-combination-sum-II.js”是一份JavaScript编程语言实现的LeetCode算法题解。LeetCode是一个在线编程平台,主要提供算法训练和面试准备题目,题目涵盖从初级到高级的不同难度级别。这道...
LeetCode上的题目设计旨在帮助程序员提升算法和数据结构的应用能力,而Combination Sum II题解的编写则是检验和加强这些技能的一个途径。因此,掌握这道题的Java解法,对于想要在求职面试中表现出色的程序员来说,是...
LeetCode题解之39-Combination Sum是一个典型的C语言算法问题,主要考察候选者对回溯算法的理解和实现能力。该问题的具体内容是找出所有相加之和为给定目标数target的组合,且每组中每个数字可以重复使用多次。解决...
在JavaScript编程中,解决算法...function combinationSum(candidates, target) { let result = []; let combination = []; // 递归函数,用于回溯搜索 function backtrack(remain, combo, start) { if (remain
java入门 java_leetcode题解之039_Combination_Sum
特别是算法题目,如216题——Combination Sum III,对于锻炼编程者的算法思维和代码实现能力有着重要作用。 Combination Sum III这道题目要求解的是找出所有和为特定值的组合,其中每个数字仅能使用一次,这些数字...
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...
- Combination Sum: 找出所有相加之和为特定值的组合。 - First Missing Positive: 找出数组中缺失的最小正数。 - Trapping Rain Water: 给定一个数组,其中每个元素代表一个宽度为1的柱子高度,计算能接多少雨水。 ...
在这个Java代码中,我们首先定义了一个名为`Solution`的类,并在其中定义了一个名为`combinationSum`的方法。该方法接收两个参数:一个整数数组`candidates`和一个整数`target`。`candidates`数组中的元素可以无限次...
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...
public int combinationSum4(int[] nums, int target) { int[] dp = new int[target + 1]; dp[0] = 1; for (int i = 1; i ; i++) { for (int num : nums) { if (i >= num) { dp[i] += dp[i - num]; } } } ...
其中,“Combination Sum III”是其中的一道典型的回溯算法题。 “Combination Sum III”题目要求给定一个范围,找出所有相加之和为特定值的k个数的组合。在这个问题中,所有数字必须是唯一的,且数字范围限制在1到...
9. **模拟和回溯**:对于某些组合优化问题,可以使用回溯法来枚举所有可能的解决方案,例如"组合总和"(Combination Sum)。 10. **排序与堆**:数组的排序问题可以通过快速排序、归并排序等经典算法解决,而"最大...
leetcode怎么计算空间复杂度是指 LeetCode-Solution my first solution of LeetCode 2015-5-7 Problem 95,98(80 already!) 我经常在递归的结束地方忘记return!!! 题型一:经典暴力递归:(里面涉及到重复不重复的...
第 296 章PY 和 GO 中的 Leetcode 我在 Python Golang ...Leetcode ...40:combination-sum-ii:传递最后选择的索引 41:先缺失正,交换 42:只是提醒:块 - 垃圾箱 43:多字符串,i+j,i+j+1 44:通配符
4. **回溯**:回溯是一种解决约束满足问题的算法,常用于“组合总和”(Combination Sum)、“N 皇后问题”(N-Queens)等。JavaScript 中回溯算法往往结合递归来实现。 5. **动态规划**:动态规划是解决优化问题的...
而回溯法常用于解决组合优化问题,如"Combination Sum"(组合求和),在Java中通常结合递归来实现。 三、深度优先搜索与广度优先搜索 DFS(深度优先搜索)和BFS(广度优先搜索)是图论和树形结构中常用的算法。Java...