C++ Solution (easy to understand but can be optimized)


  • 0
    C
    void dfs(vector<int>& nums, int curr, int S, int sign, int index, int& calcWays){
            if(index >= nums.size())
                return;
            else
                curr += sign*nums[index++];
                
            if(curr == S && index == nums.size())
                calcWays++;
                
            dfs(nums, curr, S, -1, index, calcWays);
            dfs(nums, curr, S, 1, index, calcWays);
        }
        
        int findTargetSumWays(vector<int>& nums, int S) {
            int calcWays = 0;
            dfs(nums, 0, S, -1, 0, calcWays);
            dfs(nums, 0, S, 1, 0, calcWays);
            return calcWays;
        }
    

Log in to reply
 

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