Target Sum
给一个数组, 和一个数, 问有多少种方法能用加减得到这个数. 很明显只能dfs+memo
public class Solution {
int result = 0;
public int findTargetSumWays(int[] nums, int S) {
if (nums == null || nums.length == 0) return result;
helper(nums, S, 0, 0);
return result;
}
public void helper(int[] nums, int target, int pos, long eval){
if (pos == nums.length) {
if (target == eval) result++;
return;
}
helper(nums, target, pos + 1, eval + nums[pos]);
helper(nums, target, pos + 1, eval - nums[pos]);
}
}