★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）➤博客园地址：山青咏芝（）➤GitHub地址：➤原文地址： ➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★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: 5Explanation: -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 = 3There 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.
给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例 1:
输入: nums: [1, 1, 1, 1, 1], S: 3输出: 5解释: -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一共有5种方法让最终目标和为3。
注意:
- 数组的长度不会超过20，并且数组中的值全为正数。
- 初始的数组的和不会超过1000。
- 保证返回的最终结果为32位整数。
Runtime: 160 ms
Memory Usage: 3.9 MB
1 class Solution { 2 func findTargetSumWays(_ nums: [Int], _ S: Int) -> Int { 3 var sum:Int = 0 4 for n in nums 5 { 6 sum += n 7 } 8 return sum < S || (S + sum) % 2 > 0 ? 0 : subsetSum(nums, (S + sum) >> 1) 9 }10 11 func subsetSum(_ nums: [Int], _ S: Int) -> Int12 {13 var dp:[Int] = [Int](repeating:0,count:S + 1)14 dp[0] = 115 for n in nums16 {17 if n <= S18 {19 for i in (n...S).reversed()20 {21 dp[i] += dp[i - n]22 23 }24 }25 26 }27 return dp[S]28 }29 } 216ms
1 class Solution { 2 func findTargetSumWays(_ nums: [Int], _ S: Int) -> Int { 3 var cache: [[Int: Int]] = Array(repeating: [:], count: nums.count) 4 return helper(nums, 0, S, &cache) 5 } 6 7 private func helper(_ nums: [Int], _ index: Int, _ S: Int, _ cache: inout [[Int: Int]]) -> Int { 8 if index >= nums.count { 9 return S == 0 ? 1 : 010 }11 if let res = cache[index][S] {12 return res13 }14 15 let a = -nums[index] + helper(nums, index + 1, S + nums[index], &cache)16 let b = nums[index] + helper(nums, index + 1, S - nums[index], &cache)17 cache[index][S] = a + b18 return a + b19 }20 } 280ms
1 class Solution { 2 func findTargetSumWays(_ nums: [Int], _ S: Int) -> Int { 3 var dp = [Int: Int]() 4 var f = 0 5 6 // init 7 dp[nums[0]] = 1 8 dp[-nums[0]] = 1 9 10 for i in 1.. 528ms
1 class Solution { 2 func findTargetSumWays(_ nums: [Int], _ S: Int) -> Int { 3 var dic = [0:1] 4 for num in nums { 5 var curDic = [Int : Int]() 6 7 for (key, value) in dic { 8 if let curNumAdd = curDic[key + num] { 9 curDic[key + num] = curNumAdd + value10 } else {11 curDic[key + num] = value12 }13 14 if let curNumMinus = curDic[key - num] {15 curDic[key - num] = curNumMinus + value16 } else {17 curDic[key - num] = value18 }19 }20 dic = curDic21 }22 return dic[S] ?? 023 }24 } 1312ms
1 class Solution { 2 func findTargetSumWays(_ nums: [Int], _ S: Int) -> Int { 3 return numsOfPaths(nums, S, currentIndex: 0, sumSoFar: 0) 4 } 5 6 func numsOfPaths(_ nums: [Int], _ S: Int, currentIndex: Int, sumSoFar: Int) -> Int { 7 let elem = nums[currentIndex] 8 if currentIndex == nums.count - 1 { 9 var result = 010 if S == sumSoFar + elem {11 result += 112 }13 if S == sumSoFar - elem {14 result += 115 } 16 return result17 }18 19 return numsOfPaths(nums, S, currentIndex: currentIndex + 1, sumSoFar: sumSoFar + elem) +20 numsOfPaths(nums, S, currentIndex: currentIndex + 1, sumSoFar: sumSoFar - elem)21 }22 } 2240ms
1 class Solution { 2 func findTargetSumWays(_ nums: [Int], _ S: Int) -> Int { 3 var dps: [String: Int] = [:] 4 return findTargetSumWays(nums, S, 0, &dps) 5 } 6 7 func findTargetSumWays(_ nums: [Int], _ S: Int, _ index: Int, _ dps: inout [String: Int]) -> Int { 8 let key = "\(index)-\(S)" 9 if let count = dps[key] {10 return count11 }12 13 guard index < nums.count else {14 if S == 0 {15 return 116 } else {17 return 018 }19 }20 21 let count = findTargetSumWays(nums, S - nums[index], index + 1, &dps)22 let count2 = findTargetSumWays(nums, S - (-nums[index]), index + 1, &dps)23 dps[key] = count + count224 return count + count225 }26 } 2868ms
1 class Solution { 2 func findTargetSumWays(_ nums: [Int], _ S: Int) -> Int { 3 func findTargetSumWays(_ nums: [Int], index: Int, S: Int, sum: Int) -> Int { 4 var res = 0 5 6 if index == nums.count { 7 return sum == S ? res + 1 : res 8 } 9 10 res += findTargetSumWays(nums, index: index + 1, S: S, sum: sum + nums[index])11 res += findTargetSumWays(nums, index: index + 1, S: S, sum: sum - nums[index])12 13 return res14 }15 16 return findTargetSumWays(nums, index: 0, S: S, sum: 0)17 }18 } 3156ms
1 class Solution { 2 func findTargetSumWays(_ nums: [Int], _ S: Int) -> Int { 3 return helper(nums, 0, S) 4 } 5 6 private func helper(_ nums: [Int], _ index: Int, _ S: Int) -> Int { 7 if index >= nums.count { 8 return S == 0 ? 1 : 0 9 }10 11 let a = -nums[index] + helper(nums, index + 1, S + nums[index])12 let b = nums[index] + helper(nums, index + 1, S - nums[index])13 return a + b14 }15 }