leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0494.cpp (1105B)

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