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


  • 0

    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
    

Log in to reply
 

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