LeetCode 494. Target Sum

版权声明:本文为博主原创文章,转载请注明出处,谢谢!

版权声明:本文为博主原创文章,转载请注明出处:http://blog.jerkybible.com/2017/02/08/LeetCode-494-Target-Sum/

访问原文「LeetCode 494. 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.

题意解析

给一串数字,看有几种只使用+-两种运算可以得到一个给定的数字。

解法分析

这道题的主要解法就是递归加回溯了。与Zuma Game相似但又简单很多。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public int findTargetSumWays(int[] nums, int S) {
if(nums == null || nums.length == 0){
return 0;
}
return findWays(nums, 0, S, 0);
}
private int findWays(int[] nums, int step, int S, int curSum) {
if (step == nums.length) {
if (curSum == S) {
return 1;
} else {
return 0;
}
}
int correctNumbers = 0;
for (int i = 0; i < 2; i++) {
if(i == 0){
curSum += nums[step];
correctNumbers += findWays(nums, step+1, S, curSum);
curSum -= nums[step];
}else{
curSum -= nums[step];
correctNumbers += findWays(nums, step+1, S, curSum);
curSum += nums[step];
}
}
return correctNumbers;
}