Target Sum
给一个数组, 和一个数, 问有多少种方法能用加减得到这个数. 很明显只能dfs+memo
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
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]); } } |