You are given an integer array nums
and an integer target
.
You want to build an expression out of nums by adding one of the symbols '+'
and '-'
before each integer in nums and then concatenate all the integers.
- For example, if
nums = [2, 1]
, you can add a'+'
before2
and a'-'
before1
and concatenate them to build the expression"+2-1"
.
Return the number of different expressions that you can build, which evaluates to target
.
Example 1:
Input: nums = [1,1,1,1,1], target = 3 Output: 5 Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3. -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3
Example 2:
Input: nums = [1], target = 1 Output: 1
Constraints:
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
目标和。
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ,然后串联起所有整数,可以构造一个 表达式 :
例如,nums = [2, 1] ,可以在 2 之前添加 '+' ,在 1 之前添加 '-' ,然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/target-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这道题是一道动态规划中经典的背包问题,问的是有多少种可能性。我提供三种做法。
首先是DFS + backtracking。对于 input 数组中的任何一个数字,我们既可以做加法,也可以做减法,所以为了得到最后的结果 target,我们只能不断地尝试各种组合。最后的退出条件也很简单,遍历到数组末尾同时数字的和 == target,则说明找到一组可行解了。
时间O(2^n)
空间O(n)
Java实现
1 class Solution { 2 int count = 0; 3 4 public int findTargetSumWays(int[] nums, int target) { 5 helper(nums, target, 0, 0); 6 return count; 7 } 8 9 private void helper(int[] nums, int target, int index, int sum) { 10 if (index == nums.length) { 11 if (sum == target) { 12 count++; 13 } 14 } else { 15 helper(nums, target, index + 1, sum + nums[index]); 16 helper(nums, target, index + 1, sum - nums[index]); 17 } 18 } 19 }
第二种做法是加了 memo 的 backtracking。思路跟第一种做法类似,但是用了 hashmap 记录中间结果,加快速度。代码中的encode记录的是前 X 个数字能组成的 sum 是多少,hashmap 存的是同样一个 encode 出现了多少次。
时间O(2^n)
空间O(n)
Java实现
1 class Solution { 2 public int findTargetSumWays(int[] nums, int target) { 3 // corner case 4 if (nums == null || nums.length == 0) { 5 return 0; 6 } 7 return helper(nums, 0, 0, target, new HashMap<>()); 8 } 9 10 private int helper(int[] nums, int index, int sum, int target, HashMap<String, Integer> map) { 11 String encode = index + "->" + sum; 12 if (map.containsKey(encode)) { 13 return map.get(encode); 14 } 15 if (index == nums.length) { 16 return sum == target ? 1 : 0; 17 } 18 // int cur = nums[index]; 19 int add = helper(nums, index + 1, sum - nums[index], target, map); 20 int minus = helper(nums, index + 1, sum + nums[index], target, map); 21 map.put(encode, add + minus); 22 return add + minus; 23 } 24 }
第三种做法是动态规划,思路类似coin change,也是属于背包问题。我参考了这个帖子。这里我们需要一个二维数组,表示前 i 个数字有多少种办法能计算出sum j。这里的base case是dp[0][sum] = 0,前 0 个数字只能计算出sum = 0。动态规划的转移方程是
- dp[i][j] += dp[i - 1][j + nums[i - 1]], if j + nums[i - 1] <= sum * 2
- dp[i][j] += dp[i - 1][j - nums[i - 1]], if j - nums[i - 1] >= 0
时间O(n^2)
空间O(n^2)
Java实现
1 class Solution { 2 public int findTargetSumWays(int[] nums, int target) { 3 int sum = 0; 4 for (int num : nums) { 5 sum += num; 6 } 7 8 // corner case 9 if (nums.length == 0) { 10 return 0; 11 } 12 // corner case: when target is out of range [-sum, sum] 13 if (target < -sum || target > sum) { 14 return 0; 15 } 16 17 int[][] dp = new int[nums.length + 1][sum * 2 + 1]; 18 dp[0][sum] = 1; 19 int leftBound = 0; 20 int rightBound = sum * 2; 21 for (int i = 1; i <= nums.length; i++) { 22 for (int j = leftBound; j < rightBound + 1; j++) { 23 // try all possible sum of (previous sum j + current number nums[i - 1]) and all possible difference of 24 // (previous sum j - current number nums[i - 1]) 25 if (j + nums[i - 1] <= rightBound) { 26 dp[i][j] += dp[i - 1][j + nums[i - 1]]; 27 } 28 if (j - nums[i - 1] >= leftBound) { 29 dp[i][j] += dp[i - 1][j - nums[i - 1]]; 30 } 31 } 32 } 33 return dp[nums.length][sum + target]; 34 } 35 } 36 37 /** 38 * sub-problem: dp[i][j] represents number of possible ways to reach sum j by using first ith items 39 * base case: dp[0][sum], position sum represents sum 0 40 * recurrence relation: 41 * dp[i][j] += dp[i - 1][j + nums[i - 1]] if j + nums[i - 1] <= sum * 2 42 * dp[i][j] += dp[i - 1][j - nums[i - 1]] if j - nums[i - 1] >= 0 43 * 44 * explanation: if j + nums[i - 1] or j - nums[i - 1] is in correct range, we can use the number nums[i - 1] 45 * to generate next state of dp array 46 * */ 47 // Time, O(n^2), Space, O(n^2)