leetcode

0 // Initial solution

1 class Solution {

2 public:

3 int findTargetSumWays(vector<int> &nums, int target) {

4 unordered_map<int, int> crnt;

5 crnt[0] = 1;

6 for (int i = 0; i < nums.size(); i++) {

7 unordered_map<int, int> next;

8 for (auto &p : crnt) {

9 next[p.first + nums[i]] += p.second;

10 next[p.first - nums[i]] += p.second;

11 }

12 crnt = next;

13 }

14 return crnt[target];

15 }

16 };

17

18 // Optimized using array;

19 class Solution {

20 public:

21 int findTargetSumWays(vector<int> &nums, int target) {

22 int total = accumulate(nums.begin(), nums.end(), 0);

23 vector<int> dp(2 * total + 1);

24 dp[total] = 1;

25 for (int i = 0; i < nums.size(); i++) {

26 vector<int> next(2 * total + 1);

27 for (int j = 0; j < dp.size(); j++) {

28 if (!dp[j]) continue;

29 next[j + nums[i]] += dp[j];

30 next[j - nums[i]] += dp[j];

31 }

32 dp = next;

33 }

34 return abs(target) > total ? 0 : dp[target + total];

35 }

36 };