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.
解题：
- 使用两次递归方式：分别加上当前值进行递归，减去当前值进行递归。
- 判断是否能找到解
将数组元素A分为两个集合P， N，其中P为中元素都进行加法，N中元素都进行减法。
如果存在 ：sum(P) – sum(N) = target
=> sum(P) – sum(N) + sum(P) + sum(N) = target + sum(P) + sum(N)
=> sum(P) – sum(N) + sum(P) + sum(N) = target + sum(P) + sum(N)
=> 2*sum(P) = target + sum(A)
=> sum(P) = ( target + sum(A) ) / 2
=> ( target + sum(A) ) 为偶数 ( target + sum(A) ) %2 ==0
实现：
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum < S||(sum+S)%2 == 1)
return 0;
int res = 0;
dfs(nums, 0, S, res);
return res;
}
void dfs(vector<int>& nums, int start, long int S, int& cnt){
if (start >= nums.size()){
if (S == 0) {
++cnt;
}
return;
}
dfs(nums, start+1, S-nums[start], cnt);
dfs(nums, start+1, S+nums[start], cnt);
}
};
时间复杂度 O(2^n)
空间复杂度 O(n)解题：
- 根据 sum(P) = ( target + sum(A) ) / 2 将问题转化为找到一些说的和满足此条件即可，这就成了一个最经典的
0-1背包问题。
实现：
class Solution{
private:
int subsetSum(vector<int> &nums, int S){
vector<int > dp(S+1, 0);
dp[0] = 1;
for (int n :nums){
for (int i= S; i>=n; --i)
{
dp[i] += dp[i-n];
}
}
return dp[S];
}
public:
int findTargetSumWays(vector<int>& nums, int S){
int sum = accumulate(nums.begin(), nums.end(), 0);
return sum < S || (sum + S) % 2?0:subsetSum(nums, (sum+S)/2);
}
};
时间复杂度 O(sum*n)
空间复杂度 O(n)
Be First to Comment