java - Java 添加错误 Leetcode 39 组合问题
问题描述
我正在尝试解决 leetcode 39 组合问题。我发现算法将所有数字相加并减去最后一个数字。它总是输出错误的数字。
以下是我的解决方案。
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<> ();
// corner case
if (candidates == null || candidates.length == 0 || target == 0) return res;
dfsHelper(res, candidates, target, new ArrayList<> (), 0);
return res;
}
private void dfsHelper(List<List<Integer>> res, int[] candidates, int target, List<Integer> cur, int sum) {
// base case
if (sum == target) {
Collections.sort(cur);
System.out.println(target);
if (!res.contains(cur)) {
res.add(new ArrayList<> (cur));
}
return;
} else if (sum > target) {
return;
}
// recursion
for (int i = 0; i < candidates.length; i++) {
cur.add(candidates[i]);
sum += candidates[i];
System.out.println("****");
System.out.println(cur);
System.out.println(sum);
dfsHelper(res, candidates, target, cur, sum);
//recover
sum = sum - candidates[i];
cur.remove(cur.size() - 1);
}
return;
}
}
我使用了一个测试用例,其中 target = 8, Candidates = [2,3,5] 并打印出所有 curList 和 sum。
[2] 2
[2, 2] 4
[2, 2, 2] 6
[2, 2, 2, 2] 8 8
[2, 2, 2, 3] 9
[2, 2, 2, 5] 11
[2, 2, 3] 7
[2, 2, 3, 2] 9
[2, 2, 3, 3] 10
[2, 2, 3, 5] 12
[2, 2, 5] 9
[2, 3] 5
[2, 3, 2] 7
[2, 3, 2, 2] 9
[2, 3, 2, 3] 10
[2, 3, 2, 5] 12
[2, 3, 3] 8 8
[2, 3, 5] 10
[2, 5] 7
[2, 5, 2] 9
[2, 5, 3] 10
[2, 5, 5] 12
[3] 3
[3, 2] 5
[3, 2, 2] 7
[3, 2, 2, 2] 9
[3, 2, 2, 3] 10
[3, 2, 2, 5] 12
[3, 2, 3] 8 8
[2, 3, 5] 10
[2, 3] 6
[2, 3, 2] 8 8
对于最后的输出,您可以很容易地发现 java 计算错误。我想知道这是怎么发生的。
解决方案
推荐阅读
- android - 如果 google play 上的应用程序进行逆向工程,崩溃是否会出现在我的应用程序在 google play 控制台上的崩溃中?
- python - 通过 lambda 计算百分比变化的 Python 数据框
- python - 在 numexpr 表达式中使用对象属性
- linux - 行间的 sed 模式匹配
- python - 为什么张量流中的随机数生成器 tf.random_uniform 比等效的 numpy 快得多
- tomcat - 如何为每个tomcat服务器实例编写唯一的日志文件?
- c++ - 为什么`static_cast
(uint32_t)` 工作出乎意料? - performance - 加快批处理文件解析时间
- python-3.x - 具有特定对象属性的全局缓存作为python中的输入
- c++ - 删除不同线程中的对象会导致崩溃?