# 7-liner DFS with memorization and early termination check (detailed explanation)

• Key Observation:

1. Note that any `x` and `-x` must be both odd or even, so there is no solution if `sum` of array `a[]` and target sum `s` are different in `%2`. (e.g., `vector<int> a(20,1), s = 5`)
2. Any zero entry `a[i]` does not contribute to sum, so it can be removed from array with a factor of `2` in counting because `+0 = -0`.
3. We can simply consider array `a` with all positive numbers. Then it is obvious that
• if `abs(s) > sum`, there is no solution; (e.g., `vector<int> a(20,1), s = 21`)
• if `abs(s) = sum`, there is only one solution, i.e., all `+` or all `-` signs. (e.g., `vector<int> a(20,1), s = 20`)

With these early termination conditions, combined with the following recursion:

• `m[i][s] = m[i-1][s-a[i]] + m[i-1][s+a[i]]`, (`m[i][s] = findTargetSumWays(a[0:i],s)`)

we have the following DFS code:

``````    int findTargetSumWays(vector<int>& a, int s) {
int sum = 0; for (int x:a) if(x) pos.push_back(x), sum += x; // set pos and sum
m.resize(pos.size());
return (s%2 != sum%2)? 0 : pow(2,a.size()-pos.size())*(pos.empty()? 1 : dfs(pos.size()-1, s, sum));
}

int dfs(int i, int s, int sum) {
return m[i].count(s)? m[i][s] : m[i][s] =
(!i||abs(s)>=sum)? (abs(s)==sum) : dfs(i-1,s-pos[i],sum-pos[i])+dfs(i-1,s+pos[i],sum-pos[i]);
}

vector<unordered_map<int,int>> m; // m[i][s] = findTargetSumWays(pos[0:i],s)
vector<int> pos; // positive numbers in a
``````

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