Version I - DFS
public class Solution {
int count = 0;
public int findTargetSumWays(int[] nums, int target) {
if (nums.length == 0) return 0;
if (nums.length == 1) {
if (nums[0] == Math.abs(target)) return 1;
else return 0;
}
dfsHelper(nums, target, 0, 0);
return count;
}
private void dfsHelper(int[] nums, int target, int sum, int index) {
if (index == nums.length && sum == target) {
count++;
}
if (index >= nums.length) return;
dfsHelper(nums, target, sum + nums[index], index + 1);
dfsHelper(nums, target, sum - nums[index], index + 1);
}
}
Version II - pure DP
a typical knapsack problem, whether minus or plus this number?
the range is [-sum, sum], add sum, then it will start from [0, 2 * sum], add one more space for 0, then the range of dp is [0, 2 * sum + 1]
the return value should be dp[sum + target]
public class Solution {
public int findTargetSumWays(int[] nums, int S) {
if (nums.length == 0) return 0;
int sum = 0;
for (int i : nums) sum += i;
if (Math.abs(S) > sum) return 0;
int[] dp = new int[2 * sum + 1];
dp[sum + 0] = 1;
for (int i = 0; i < nums.length; ++i) {
int[] tmp = new int[2 * sum + 1];
for (int j = 0; j < dp.length; ++j) {
if (dp[j] != 0) {
tmp[j + nums[i]] += dp[j];
tmp[j - nums[i]] += dp[j];
}
}
dp = tmp;
}
return dp[sum + S];
}
}