494. Target Sum
1. Description
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 ‘+’ before 2 and a ‘-’ before 1 and concatenate them to build the expression “+2-1”.
Return the number of different expressions that you can build, which evaluates to target.
2. Example
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
3. Constraints
- 1 <= nums.length <= 20
- 0 <= nums[i] <= 1000
- 0 <= sum(nums[i]) <= 1000
- -1000 <= target <= 1000
4. Solutions
Dynamic Programming
n = nums.size()
Time complexity: O(n(sum - target))
Space complexity: O(sum - target)
class Solution {
public:
int findTargetSumWays(const vector<int> &nums, int target) {
// (sum - neg) - neg = sum - 2*neg = target
// neg = (sum - target) / 2
// so we convert the problem to select numbers from nums and sum them up tp get neg
cin.tie(nullptr);
std::ios::sync_with_stdio(false);
int nega_num_sum = accumulate(nums.begin(), nums.end(), 0) - target;
if ((nega_num_sum & 1) == 1 || nega_num_sum < 0) {
return 0;
}
nega_num_sum >>= 1;
/*
// dp[i][j] means the methods to select numbers from top i to form the sum of j
vector<vector<int>> dp(nums.size() + 1, vector<int>(nega_num_sum + 1));
dp[0][0] = 1;
for (int i = 1; i <= nums.size(); ++i) {
for (int j = 0; j <= nega_num_sum; ++j) {
dp[i][j] = dp[i - 1][j];
if (j >= nums[i - 1]) {
dp[i][j] += dp[i - 1][j - nums[i - 1]];
}
}
}
return dp[nums.size()][nega_num_sum];
*/
vector<int> dp(nega_num_sum + 1);
dp[0] = 1;
for (int i = 1; i <= nums.size(); ++i) {
for (int j = nega_num_sum; j >= nums[i - 1]; --j) {
dp[j] += dp[j - nums[i - 1]];
}
}
return dp.back();
}
};