You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols
+
and -
. For each integer, you should choose one from +
and -
as its new symbol.
Find out how many ways to assign symbols to make sum of integers equal to target S.
Example 1:
Input: nums is [1, 1, 1, 1, 1], S is 3. Output: 5 Explanation: -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 There are 5 ways to assign symbols to make the sum of nums be target 3.
Note:
- The length of the given array is positive and will not exceed 20.
- The sum of elements in the given array will not exceed 1000.
- Your output answer is guaranteed to be fitted in a 32-bit integer.
---------------------------
Solution #1, straightforward recursionO(2^n)
class Solution { public int findTargetSumWays(int[] nums, int S) { return helper(nums, 0, S); } private int helper(int[] nums, int index, int sum) { if (index == nums.length && sum == 0) return 1; if (index >= nums.length) return 0; return helper(nums, index + 1, sum - nums[index]) + helper(nums, index + 1, sum + nums[index]); } }Solution #2
Memoization
会发现此题有重复的子问题,DP可解:
+ 1 - 1 [11] 跟 - 1 + 1 [11], 括号内为重复
+ 1 + 2 - 3 [4 5 6] 跟 - 1 - 2 + 3 [4 5 6]
很难直接从递归就看出它的复杂度,因为取决于生成不同sum的个数。树的深度为nums的长度
class Solution {
public int findTargetSumWays(int[] nums, int S) { return helper(nums, 0, S, new HashMapSolution #3,遍历DP,跟上面Memoization一样,每一个小问题都可以用(index, sum)的组合来表示()); } private int helper(int[] nums, int index, int sum, Map cache) { if (index == nums.length && sum == 0) return 1; if (index >= nums.length) return 0; String plusKey = index + "+" + sum; int plus = 0; if (cache.containsKey(plusKey)) { plus = cache.get(plusKey); } else { plus = helper(nums, index + 1, sum - nums[index], cache); cache.put(plusKey, plus); } String minusKey = index + "-" + sum; int minus = 0; if (cache.containsKey(minusKey)) { minus = cache.get(minusKey); } else { minus = helper(nums, index + 1, sum + nums[index], cache); cache.put(minusKey, minus); } return plus + minus; } }
O(n * m) 时间,n为nums的changdu,m为最长的sums的可能性
class Solution { public int findTargetSumWays(int[] nums, int S) { int n = nums.length; Mapsums = new HashMap<>(); Map newSums = new HashMap<>(); sums.put(S, 1); for (int i = n - 1; i >= 0; i--) { int num = nums[i]; for (Map.Entry pair : sums.entrySet()) { int sum1 = pair.getKey() - num; addToNewMap(newSums, sum1, pair.getValue()); int sum2 = pair.getKey() + num; addToNewMap(newSums, sum2, pair.getValue()); } Map tmp = sums; sums.clear(); sums = newSums; newSums = tmp; } return sums.getOrDefault(0, 0); } private void addToNewMap(Map cur, int sum, int value) { if (!cur.containsKey(sum)) { cur.put(sum, 0); } cur.put(sum, value + cur.get(sum)); } }
其他:因为题目已经给定所有数的sum不会超过1000,所以有一种方法是开一个大小为1000(?或者2000 + 1,因为要考虑0和负数)的数组,每次遍历一下就是了。
但是以上我的方法不会被1000所限制。
Update: 发现Solution #2-#3原来就是所谓的subset sum
No comments:
Post a Comment