C++ iterative with unordered_map


  • 10
    // OJ: https://leetcode.com/problems/target-sum
    // Author: github.com/lzl124631x
    // Time: O(2^N)
    // Space: O(2^N)
    class Solution {
    public:
      int findTargetSumWays(vector<int>& nums, int S) {
        unordered_map<int, int> ans;
        ans[0] = 1;
        for (int n : nums) {
          unordered_map<int, int> newAns;
          for (auto p : ans) {
            int sum = p.first, cnt = p.second;
            newAns[sum + n] += cnt;
            newAns[sum - n] += cnt;
          }
          ans = newAns;
        }
        return ans[S];
      }
    };
    

    Updated with other solutions

    // OJ: https://leetcode.com/problems/target-sum
    // Author: github.com/lzl124631x
    // Time: O(2^N)
    // Space: O(N)
    class Solution {
    private:
      int cnt = 0;
      void dfs(vector<int>& nums, int S, int start) {
        if (start == nums.size()) {
          cnt += !S;
          return;
        }
        dfs(nums, S + nums[start], start + 1);
        dfs(nums, S - nums[start], start + 1);
      }
    public:
      int findTargetSumWays(vector<int>& nums, int S) {
        dfs(nums, S, 0);
        return cnt;
      }
    };
    
    // OJ: https://leetcode.com/problems/target-sum
    // Author: github.com/lzl124631x
    // Time: O(2^N)
    // Space: O(2^N)
    class Solution {
    private:
      vector<unordered_map<int, int>> memo;
      int dfs(vector<int>& nums, int S, int start) {
        if (start == nums.size()) return !S ? 1 : 0;
        if (memo[start].count(S)) return memo[start][S];
        return memo[start][S] = dfs(nums, S + nums[start], start + 1)
                                + dfs(nums, S - nums[start], start + 1);
      }
    public:
      int findTargetSumWays(vector<int>& nums, int S) {
        memo = vector<unordered_map<int, int>>(nums.size());
        return dfs(nums, S, 0);
      }
    };
    
    // OJ: https://leetcode.com/problems/target-sum
    // Author: github.com/lzl124631x
    // Time: O(NS)
    // Space: O(S)
    // Ref: https://discuss.leetcode.com/topic/76243/java-15-ms-c-3-ms-o-ns-iterative-dp-solution-using-subset-sum-with-explanation
    class Solution {
    private:
      int subsetSum(vector<int> &nums, int S) {
        vector<int> dp(S + 1, 0);
        dp[0] = 1;
        for (int n : nums)
          for (int i = S; i >= n; --i) dp[i] += dp[i - n];
        return dp[S];
      }
    public:
      int findTargetSumWays(vector<int>& nums, int S) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        return sum < S || (sum + S) % 2 ? 0 : subsetSum(nums, (sum + S) / 2);
      }
    };
    

  • 0
    C

    @lzl124631x Simple and it works! Could you analyze the time complexity of this method?


  • 0

    Time complexity i believe is O(2^N)


  • 0
    Z

    Time complexity of first solution is O(ns) instead of O(2^n). s is the total number of possible sums, which is between -1000 and 1000. It is dp, but use map instead of vector, so it is slower.
    If adding some optimization, the run time is comparable to dp. 35ms, 62%.

    class Solution {
    public:
        int findTargetSumWays(vector<int>& nums, int S) {
            int sum = 0;
            for (int num:nums) sum += num;
           // early termination for impossible cases
            if (abs(S) > sum || (sum-S)&1 == 1) return 0;
            int n = nums.size(), ans = 0;
           // working from left and right end towards the middle
            unordered_map<int, int> left, right;
            left[0] = 1;
            right[0] = 1;
            for (int i = 0; i < n/2; ++i) {
                unordered_map<int, int> tmp;
                for (auto it = left.begin(); it != left.end(); it++) {
                    tmp[it->first+nums[i]] += it->second;
                    tmp[it->first-nums[i]] += it->second;
                }
                swap(left, tmp);
            }
            for (int i = n/2; i < n; ++i) {
                unordered_map<int, int> tmp;
                for (auto it = right.begin(); it != right.end(); it++) {
                    tmp[it->first+nums[i]] += it->second;
                    tmp[it->first-nums[i]] += it->second;
                }
                swap(right, tmp);
            }
            for (auto it = left.begin(); it != left.end(); it++) {
                if (right.count(S-it->first)) {
                    ans += it->second*right[S-it->first];
                }
            }
            return ans;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.