LeetCode – 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. 使用两次递归方式:分别加上当前值进行递归,减去当前值进行递归。
  2.  判断是否能找到解

        将数组元素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)

解题

  1. 根据  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)

参考:

花花酱 LeetCode 494. Target Sum

 

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注