LeetCode 494. Target Sum

本文主要是介绍LeetCode 494. Target Sum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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 = 3There are 5 ways to assign symbols to make the sum of nums be target 3.

Note:

1. The length of the given array is positive and will not exceed 20.
2. The sum of elements in the given array will not exceed 1000.
3. Your output answer is guaranteed to be fitted in a 32-bit integer.

三、解题思路

• 最好的办法是用动态规划来做这道题，可以抽象成SubSet Sum的一个问题。
• 下面先给出一个分治的版本，时间复杂度是指数的，但是也能AC。思路就是从后向前考虑，假设最后一个是+或者-然后更新target的值，然后递归调用。需要注意的是退出条件，当只剩下一个数的时候，如果a[0] == abs(T) 并且不为0那么返回1，如果他们都为0，那么应该返回2，如果不相等则直接返回0；

class Solution {
public:int DP_findTSW(vector<int>&nums, int n, int S){if( n == 0 ) {if(nums[0] == 0 && S == 0) return 2;else if(nums[0] == abs(S) && nums[0] != 0) return 1;else return 0;}return DP_findTSW(nums, mem, n-1, S - nums[n]) + DP_findTSW(nums, mem, n-1, S + nums[n]);}int findTargetSumWays(vector<int>& nums, int S) {if(nums.size() == 0) return 0;return DP_findTSW(nums, nums.size()-1, S);}
};

这篇关于LeetCode 494. Target Sum的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---