# C++ iterative with unordered_map

• ``````// 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);
}
};
``````

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

• Time complexity i believe is O(2^N)

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

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