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.
A:
就是每次加入一个新的值,计算所有可能的结果。-----------关键点在于: M[0] = 1;
class Solution { public: int findTargetSumWays(vector<int>& nums, int S) { unordered_map<int, int> M; // mapping from sum value to its count M[0] = 1; for(auto v : nums) { unordered_map<int, int> N; for(auto & it:M) { N[it.first + v] += it.second; N[it.first - v] += it.second; } M = N; } return M[S]; } };
No comments:
Post a Comment