leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0494.cpp (1105B)

      1 // Initial solution
      2 class Solution {
      3   public:
      4     int findTargetSumWays(vector<int> &nums, int target) {
      5         unordered_map<int, int> crnt;
      6         crnt[0] = 1;
      7         for (int i = 0; i < nums.size(); i++) {
      8             unordered_map<int, int> next;
      9             for (auto &p : crnt) {
     10                 next[p.first + nums[i]] += p.second;
     11                 next[p.first - nums[i]] += p.second;
     12             }
     13             crnt = next;
     14         }
     15         return crnt[target];
     16     }
     17 };
     18 
     19 // Optimized using array;
     20 class Solution {
     21   public:
     22     int findTargetSumWays(vector<int> &nums, int target) {
     23         int total = accumulate(nums.begin(), nums.end(), 0);
     24         vector<int> dp(2 * total + 1);
     25         dp[total] = 1;
     26         for (int i = 0; i < nums.size(); i++) {
     27             vector<int> next(2 * total + 1);
     28             for (int j = 0; j < dp.size(); j++) {
     29                 if (!dp[j]) continue;
     30                 next[j + nums[i]] += dp[j];
     31                 next[j - nums[i]] += dp[j];
     32             }
     33             dp = next;
     34         }
     35         return abs(target) > total ? 0 : dp[target + total];
     36     }
     37 };