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相似但又简单很多。

解题代码

	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;
}