java - 几乎相同的语句,但值不同
问题描述
我正在研究一个经典的 DP 问题,Count Subset Sum。
如果您不确定该问题,则问题陈述如下:给定一组正数,找出总和等于给定数“S”的子集的总数。
我正在尝试用回溯方法解决它。
假设给定的数组是
4 [1, 1, 2, 3]
,sum
所以预期的结果是3
private int backtrack2(int[] nums, int sum) {
int[] count = new int[1];
backtrack2Helper(nums, sum, count, 0);
return count[0];
}
private int backtrack2Helper(int[] nums, int sum, int[] count, int pos) {
if (0 == sum) return 1;
if (pos == nums.length) return 0;
for (int i = pos; i < nums.length; ++i) {
if (sum - nums[i] >= 0) {
int temp = backtrack2Helper(nums, sum - nums[i], count, i + 1);
count[0] += temp;
}
}
return 0;
}
但是,下面的代码无法生成正确的结果:
private int backtrack2(int[] nums, int sum) {
int[] count = new int[1];
backtrack2Helper(nums, sum, count, 0);
return count[0];
}
private int backtrack2Helper(int[] nums, int sum, int[] count, int pos) {
if (0 == sum) return 1;
if (pos == nums.length) return 0;
for (int i = pos; i < nums.length; ++i) {
if (sum - nums[i] >= 0) {
count[0] += backtrack2Helper(nums, sum - nums[i], count, i + 1);
}
}
return 0;
}
唯一的区别是if
辅助函数中的语句部分。
int temp = backtrack2Helper(nums, sum - nums[i], count, i + 1);
count[0] += temp;
和
count[0] += backtrack2Helper(nums, sum - nums[i], count, i + 1);
应该是等价的吧?
但是第二个不能正常工作。真的是一头雾水,一步步调试,发现当第二种方式的方法最后命中return语句的时候,count[0]
不是被返回的0加上,而是设置为0。
发生了什么?
解决方案
backtrack2Helper()
差异源于变化的事实count[0]
。
例如,假设将from的backtrack2Helper(nums, sum - nums[i], count, i + 1)
值更改为并返回。count[0]
0
1
1
在一个片段中,您将更改的值添加count[0]
到递归调用返回的值中:
int temp = backtrack2Helper(nums, sum - nums[i], count, i + 1); // == 1
count[0] += temp; // == 1 + 1 == 2
但在另一个片段中,您将原始值添加count[0]
到递归调用返回的值中:
count[0] += backtrack2Helper(nums, sum - nums[i], count, i + 1); // == 0 + 1 == 1
编辑:
count[]
您可以在没有数组的情况下编写更优雅的解决方案:
private static int backtrack2(int[] nums, int sum) {
return backtrack2Helper(nums, sum, 0);
}
private static int backtrack2Helper(int[] nums, int sum, int pos) {
if (0 == sum)
return 1;
if (pos == nums.length)
return 0;
int count = 0;
for (int i = pos; i < nums.length; ++i) {
if (sum - nums[i] >= 0) {
count += backtrack2Helper(nums, sum - nums[i], i + 1);
}
}
return count;
}
编辑:
为了改进对两个片段差异的解释,这里有一个更简单的代码,它产生相同的行为:
int method2 (int[] arr)
{
arr[0] = 5;
return 0;
}
第一个片段:
void method1 ()
{
int[] arr = new int[1]; // arr[0] is 0
int temp = method2 (arr); // temp is assigned 0, arr[0] is changed to 5 by method2
arr[0] += temp // arr[0] = arr[0] + temp == 5 + 0 == 5
}
第二个片段:
void method1 ()
{
int[] arr = new int[1]; // arr[0] is 0
arr[0] += method2 (arr); // arr[0] = arr[0] + method2 (arr) == 0 + 0 == 0
}
推荐阅读
- hadoop - hdfs:现有文件上的“没有这样的文件或目录”
- java - 如何使用 MapStruct 在一个字段中应用 List?
- r - R 中的 H 查找 - 按标题名称合并数据
- django - 姜戈。查询数组参数
- oop - 继承总是可以被组合代替吗?
- reactjs - 状态应用于所有元素,而不仅仅是选定的元素
- php - 即使有更多数据要遍历数组元素,也会中断循环
- bash - `make` 二进制文件的两个不同符号链接:为什么调用的结果不同?
- android - 实现 WorkManger 时如何向 Worker 类发送 byteArray?
- wso2 - WSO2 EI,将序列分组到文件夹中