题目大意:给你一串数字,你可以在每个数字前放置+或-,问有多少种方法可以使得表达式的值等于target。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:
1 2 3 4 5 6 7 8 9 10 11 |
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.
Idea: DP
Solution 1: DP
Time complexity: O(n*sum)
Space complexity: O(n*sum)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua // Running time: 16 ms class Solution { public: int findTargetSumWays(vector<int>& nums, int S) { const int n = nums.size(); const int sum = std::accumulate(nums.begin(), nums.end(), 0); if (sum < S) return 0; const int offset = sum; // ways[i][j] means total ways to sum up to (j - offset) using nums[0] ~ nums[i - 1]. vector<vector<int>> ways(n + 1, vector<int>(sum + offset + 1, 0)); ways[0][offset] = 1; for (int i = 0; i < n; ++i) { for (int j = nums[i]; j < 2 * sum + 1 - nums[i]; ++j) if (ways[i][j]) { ways[i + 1][j + nums[i]] += ways[i][j]; ways[i + 1][j - nums[i]] += ways[i][j]; } } return ways.back()[S + offset]; } }; |
C++ SC O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua // Running time: 12 ms class Solution { public: int findTargetSumWays(vector<int>& nums, int S) { const int n = nums.size(); const int sum = std::accumulate(nums.begin(), nums.end(), 0); if (sum < std::abs(S)) return 0; const int kOffset = sum; const int kMaxN = sum * 2 + 1; vector<int> ways(kMaxN, 0); ways[kOffset] = 1; for (int num : nums) { vector<int> tmp(kMaxN, 0); for (int i = num; i < kMaxN - num; ++i) if (ways[i]) { tmp[i + num] += ways[i]; tmp[i - num] += ways[i]; } std::swap(ways, tmp); } return ways[S + kOffset]; } }; |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua // Running time: 28 ms class Solution { public int findTargetSumWays(int[] nums, int S) { int sum = 0; for (final int num : nums) sum += num; if (sum < S) return 0; final int kOffset = sum; final int kMaxN = sum * 2 + 1; int[] ways = new int[kMaxN]; ways[kOffset] = 1; for (final int num : nums) { int[] tmp = new int[kMaxN]; for (int i = num; i < kMaxN - num; ++i) { tmp[i + num] += ways[i]; tmp[i - num] += ways[i]; } ways = tmp; } return ways[S + kOffset]; } } |
C++ / V2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua // Running time: 17 ms class Solution { public: int findTargetSumWays(vector<int>& nums, int S) { const int n = nums.size(); const int sum = std::accumulate(nums.begin(), nums.end(), 0); if (sum < std::abs(S)) return 0; const int kOffset = sum; const int kMaxN = sum * 2 + 1; vector<int> ways(kMaxN, 0); ways[kOffset] = 1; for (int num : nums) { vector<int> tmp(kMaxN, 0); for (int i = 0; i < kMaxN; ++i) { if (i + num < kMaxN) tmp[i] += ways[i + num]; if (i - num >= 0) tmp[i] += ways[i - num]; } std::swap(ways, tmp); } return ways[S + kOffset]; } }; |
Solution 2: DFS
Time complexity: O(2^n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua // Running time: 422 ms class Solution { public: int findTargetSumWays(vector<int>& nums, int S) { const int sum = std::accumulate(nums.begin(), nums.end(), 0); if (sum < std::abs(S)) return 0; int ans = 0; dfs(nums, 0, S, ans); return ans; } private: void dfs(const vector<int>& nums, int d, int S, int& ans) { if (d == nums.size()) { if (S == 0) ++ans; return; } dfs(nums, d + 1, S - nums[d], ans); dfs(nums, d + 1, S + nums[d], ans); } }; |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua // Running time: 615 ms class Solution { private int ans; public int findTargetSumWays(int[] nums, int S) { int sum = 0; for (final int num : nums) sum += num; if (sum < Math.abs(S)) return 0; ans = 0; dfs(nums, 0, S); return ans; } private void dfs(int[] nums, int d, int S) { if (d == nums.length) { if (S == 0) ++ans; return; } dfs(nums, d + 1, S - nums[d]); dfs(nums, d + 1, S + nums[d]); } } |
Solution 3: Subset sum
Time complexity: O(n*sum)
Space complexity: O(sum)
C++ w/ copy
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua // Running time: 7 ms class Solution { public: int findTargetSumWays(vector<int>& nums, int S) { S = std::abs(S); const int sum = std::accumulate(nums.begin(), nums.end(), 0); if (sum < S || (S + sum) % 2 != 0) return 0; const int target = (S + sum) / 2; vector<int> dp(target + 1, 0); dp[0] = 1; for (int num : nums) { vector<int> tmp(dp); for (int j = 0; j <= target - num; ++j) tmp[j + num] += dp[j]; std::swap(dp, tmp); } return dp[target]; } }; |
C++ w/o copy
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua // Running time: 6 ms class Solution { public: int findTargetSumWays(vector<int>& nums, int S) { S = std::abs(S); const int n = nums.size(); const int sum = std::accumulate(nums.begin(), nums.end(), 0); if (sum < S || (S + sum) % 2 != 0) return 0; const int target = (S + sum) / 2; vector<int> dp(target + 1, 0); dp[0] = 1; for (int num : nums) for (int j = target; j >= num; --j) dp[j] += dp[j - num]; return dp[target]; } }; |