leetcode494.Target Sum

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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的集合的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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];
}