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