Almost the same statements, but different value

user_6797890 0
Viewed 48

I'm working on a classic DP question, Count Subset Sum.

The problem statement is as follows if you are not sure about the problem: Given a set of positive numbers, find the total number of subsets whose sum is equal to a given number ‘S’.

I'm trying to work solve it with backtracking approach.

Assume the given array is [1, 1, 2, 3] and the sum is 4, so the expected result is 3
The weird thing is the code blow works fine, and it generates the correct result.

  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;
  }

However, the code below can not generate the correct result:

  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;
  }

The only difference is the if statement part in the helper function.

int temp = backtrack2Helper(nums, sum - nums[i], count, i + 1);
count[0] += temp;

and 

count[0] += backtrack2Helper(nums, sum - nums[i], count, i + 1);

should be equivalent, right?

But the second one does not work correctly. I was really confused and I debugged it step by step, finding that when the method in the second approach hit the return statement at last, count[0] was not added by the returned 0, but set to 0.

What's happening?

backtracking return java
1 Answers

The difference results from the fact that backtrack2Helper() changes count[0].

Suppose, for example, that backtrack2Helper(nums, sum - nums[i], count, i + 1) changes that value of count[0] from 0 to 1 and returns 1.

In one snippet you are adding the changed value of count[0] to the value returned by the recursive call:

int temp = backtrack2Helper(nums, sum - nums[i], count, i + 1); // == 1
count[0] += temp; // == 1 + 1 == 2

But in the other snippet you are adding the original value of count[0] to the value returned by the recursive call:

count[0] += backtrack2Helper(nums, sum - nums[i], count, i + 1); // == 0 + 1 == 1

EDIT:

You can write a more elegant solution without the count[] array:

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;
}

EDIT:

To improve the explanation regarding the difference of the two snippets, here's a simpler code that produces the same behavior:

int method2 (int[] arr)
{
   arr[0] = 5;
   return 0; 
}

First snippet:

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
}

Second snippet:

void method1 ()
{
    int[] arr = new int[1]; // arr[0] is 0
    arr[0] += method2 (arr); // arr[0] = arr[0] + method2 (arr) == 0 + 0 == 0
}
user_12215710
Related