[C++] 1 liner


  • -1

    1 liner

    class Solution {
    public:
        int findTargetSumWays(vector<int>& a, int S, int i = 0) {
            return i == a.size() ? S == 0 : findTargetSumWays(a, S - a[i], i + 1) + findTargetSumWays(a, S + a[i], i + 1);
        }
    };
    

    2 liner

    class Solution {
    public:
        int findTargetSumWays(vector<int>& a, int sum) {
            return find(a, sum, 0);
        }
    private:
        int find(vector<int>& a, int sum, int i) {
            return i == a.size() ? sum == 0 : find(a, sum - a[i], i + 1) + find(a, sum + a[i], i + 1);
        }
    };
    

    Check absolute sum left to stop search

    class Solution {
    public:
        int findTargetSumWays(vector<int>& a, int sum) {
            int absum = std::accumulate(a.begin(), a.end(), 0);
            return find(a, sum, 0, absum);
        }
    
    private:
        int find(vector<int>& a, int sum, int i, int absum) {
            return i == a.size() ? sum == 0 : (absum < abs(sum) ? 0 : find(a, sum - a[i], i + 1, absum - a[i]) + find(a, sum + a[i], i + 1, absum - a[i]));
        }
    };
    

Log in to reply
 

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