494 Target Sum
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:
- 1.The length of the given array is positive and will not exceed 20.
- 2.The sum of elements in the given array will not exceed 1000.
- 3.Your output answer is guaranteed to be fitted in a 32-bit integer.
(1) DFS
public class Solution {
public int findTargetSumWays(int[] nums, int S) {
int[] res = new int[1];
findTargetSum(0, 0, S, nums, res);
return res[0];
}
public void findTargetSum(int index, int curSum, int target, int[] nums, int[] res) {
if (index == nums.length) {
if (curSum == target) {
++res[0];
}
return;
}
findTargetSum(index + 1, curSum + nums[index], target, nums, res);
findTargetSum(index + 1, curSum - nums[index], target, nums, res);
}
}
（2) 2D DP
class Solution {
public int findTargetSumWays(int[] nums, int S) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum < S || (sum + S) % 2 != 0) {
return 0;
}
return getWaysToSubsetSum(nums, (sum + S)/2);
}
public int getWaysToSubsetSum(int[] nums, int target) {
int n = nums.length;
int[][] dp = new int[n + 1][target + 1];
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
// Target要从0开始
for (int j = 0; j <= target; j++) {
if (nums[i - 1] <= j) {
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
}
else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][target];
}
}
(3) 1D DP
class Solution {
public int findTargetSumWays(int[] nums, int S) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum < S || (sum + S) % 2 != 0) {
return 0;
}
return getWaysToSubsetSum(nums, (sum + S)/2);
}
public int getWaysToSubsetSum(int[] nums, int target) {
int n = nums.length;
int[] dp = new int[target + 1];
dp[0] = 1;
// 0-1背包模板
for (int i = 0; i < n; i++) {
for (int j = target; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[target];
}
}
DFS: 时间复杂度O(2^n), 空间复杂度O(2^n)
2D DP: 时间复杂度O(n * target), 空间复杂度O(n * target)
1D DP: 时间复杂度O(n * target), 空间复杂度O(target)
Last modified 3yr ago