几乎相同的陈述，但不同的价值

Question

我正在做一道经典的 DP 题，Count Subset Sum。

如有不明白的问题陈述如下：给定一组正数，找出总和等于给定数“S”的子集的总数。

我正在尝试使用回溯方法解决它。

假设给定的数组是[1, 1, 2, 3]，sum是4，所以预期结果是3
奇怪的是代码 blow 工作正常，并且生成了正确的结果。

  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语句时，returned 0没有添加count[0]，但设置为 0。

发生了什么事？

Answer 1

不同之处在于 backtrack2Helper() 更改 count[0]。

例如，假设 backtrack2Helper(nums, sum - nums[i], count, i + 1) 将 count[0] 的值从 0 更改为 1 和 returns 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
}

几乎相同的陈述，但不同的价值

Almost the same statements, but different value

java

return

backtracking