leetcode494. Target Sum

RobinTang 发布于2019-08-15 14:32 / 1672人阅读

摘要：为了寻找合适的正负号赋值，我们其实可以将数组分为两个子集，其中一个子集中的数字都被赋予了正号，而另一个子集中的数字都被赋予了负号。如果二者的和不是一个偶数，就一定无法找到这样的正负号集合使得其结果为。

题目要求

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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