Simple dfs solution.


  • 2
    M

    Simple dfs solution.
    branch to plus and minus, when index hits the end of array return 1 when the target is zero (found), otherwise 0 (not found).

    public int findTargetSumWays(int[] nums, int S) {
            return helper(nums, 0, S);
        }
        
        private int helper(int[] nums, int idx, int S) {
            if (idx == nums.length) {
                return S == 0 ? 1 : 0;
            }
            
            int plus = helper(nums, idx+1, S+nums[idx]);
            int minus = helper(nums, idx+1, S-nums[idx]);
            
            return plus + minus;
        }
    

Log in to reply
 

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