leetcode494. Target Sum

RobinTang 發布于2019-08-15 14:32 / 1675人閱讀

摘要：為了尋找合適的正負號賦值，我們其實可以將數組分為兩個子集，其中一個子集中的數字都被賦予了正號，而另一個子集中的數字都被賦予了負號。如果二者的和不是一個偶數，就一定無法找到這樣的正負號集合使得其結果為。

題目要求

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.

現在有一個整數數組，你需要為每一個數組賦予正號或是負號，使其的和為目標值。

思路一：廣度優先遍歷

直觀的來說，我們可以將所有的情況都嘗試一遍并且將可能構成結果的集合統計下來。就以題目中例子來說，原始的輸入為[1,1,1,1,1]，目標值為3。那么我們假設先給第一個值設置為正數，則只需要知道[1,1,1,1]組合成目標值2的集合個數即可。通過不斷的遞歸調用，當遍歷到數組的盡頭時，我們只需要知道當前的目標值是否為0，如果為0，說明該嘗試成功并返回1，否則返回0。

    public int findTargetSumWays(int[] nums, int S) {
        return findTargetSumWays(nums, 0, S);
    }
    
    public int findTargetSumWays(int[] nums, int start, int S){
        if(start==nums.length){
            if(S == 0){
                return 1;
            }else{
                return 0;
            }
        }
        int count = 0;
        count += findTargetSumWays(nums, start+1, S-nums[start+1]);
        count += findTargetSumWays(nums, start+1, S+nums[start+1]);
        return count;
        
    }

思路二：子集查找

這個是我從網上找來的思路，但是網上的很多博客解釋的并不清楚，這里我再試著詳細的解釋一下。

為了尋找合適的正負號賦值，我們其實可以將數組分為兩個子集，其中一個子集中的數字都被賦予了正號，而另一個子集中的數字都被賦予了負號。所有的數字都將落入這兩個集合中。那么我們令正號的集合為S(P)，負號的集合為S(N)，所有數字的和為sum，目標值為target。我們可以推倒出如下結論：

S(P) + S(N) = sum
S(P) - S(N) = target
S(P) * 2 = sum + target

因此，sum和target的和一定是一個偶數。如果二者的和不是一個偶數，就一定無法找到這樣的正負號集合使得其結果為target。

因此，題目被我們轉化為從該集合中找到所有子集，每個子集需滿足其下所有數字的和為positive = (sum+target)/2。

這個問題我們可以通過動態規劃來解決。

假設我們想知道構成positive的集合有多少個，其實可以分解為以下幾個部分：

第一步，當{nums[0],nums[1]}為基數時，則

Count(positive) = Count(positive-nums[0])
Count(positive-1) = Count(positive-1-nums[0])
...
Count(nums[0]+1) = Count(0)

第二步，當{nums[0],nums[1]}為基數時，同理

Count(positive) = Count(positive-nums[0])
Count(positive-1) = Count(positive-1-nums[0])
...
Count(nums[0]+1) = Count(0)

你會發現二者的步驟居然是一樣的！因為這里采用了動態規劃的思想，第一圈遍歷之后，Count(i)上的值實際上代表著由{nums[0]}為基數和為i的集合的數量。第二圈遍歷之后，Count(i)上的值代表著由{nums[0],nums[1]}為基數時和為i的集合的數量。

因此，第n全遍歷后，Count(positive)上的值就代表著由{nums[0], nums[1]...nums[n-1]}為基數時和為positive的集合的數量。

    public int findTargetSumWays2(int[] nums, int S) {
        int sum = 0;
        for(int i = 0; i < nums.length; i++) {
            sum += Math.abs(nums[i]);
        }
        //數組中所有的值的和小于標準值 或是奇偶性不同 則直接返回
        return  sum < S || (sum + S) % 2 == 1 ? 0 : helper(nums, (sum + S) / 2);
    }
    private int helper(int[] nums, int sum) {
        //array[i]是指和為i的集合有多少個
        int[] array = new int[sum + 1];
        array[0] = 1;
        for(int i = 0; i < nums.length; i++) {
            for(int j = sum; j - nums[i] >= 0; j--) {
                array[j] += array[j - nums[i]];
            }
        }
        return array[sum];
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

云服務器 GPU云服務器 Leetcod LeetCode LeetCode_String target

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/68667.html

Leetcode 相似題只有題號不含代碼。

找出string里的單詞。 186. Reverse Words in a String II, 434. Number of Segments in a String combination類型題 77. Combinations 39. Combination Sum 40. Combination Sum II 216. Combination Sum III 494. Target S...

StonePanda 2019-08-14 18:01 評論0 收藏0
Leetcode 題解 - 雙指針

摘要：一有序數組的題目描述在有序數組中找出兩個數，使它們的和為。解題思路使用雙指針，一個指針指向值較小的元素，一個指針指向值較大的元素。輸出二兩數平方和判斷一個數是否為數平方和開平方根一、有序數組的 Two Sum Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2 題目描述：在有序數組中找出兩個數，使它們...

leanxi 2019-08-16 18:40 評論0 收藏0
[LeetCode] 416. Partition Equal Subset Sum

Problem Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal. Note:Each of the array ...

makeFoxPlay 2019-08-16 13:42 評論0 收藏0
leetcode14 4sum

摘要：這里需要注意及時處理掉重復的情況。那么就需要盡可能排除不可能的情況來提高計算效率。因為數組已經被排序，所以可以根據數組中元素的位置判斷接下來的情況是否有可能合成目標值。題目要求此處為原題地址 Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d =...

MoAir 2019-08-16 10:31 評論0 收藏0
leetcode40 combination sum 2

摘要：參考思路和非常類似，只是這里需要增加進行重復處理的部分。題目要求題目中新添的要求包括數組中存在重復值，而且數組中每個值只可以使用一次。需要注意的是，既然數組中存在重復的值，就要注意可能會將重復的情況加入結果數組。參考思路和leetcode39 combination sum 非常類似，只是這里需要增加進行重復處理的部分。請參考我對leetcode39進行解答的這篇博客。題目要求 ...

Code4App 2019-08-16 10:33 評論0 收藏0