Short Java DFS solution without global variable


  • 0
    A
    public class Solution {
        public int findTargetSumWays(int[] nums, int S) {
            return helper(nums, S, 0);
        }
        
        private int helper(int[] nums, int target, int pos) {
            if (pos == nums.length) {
                if (target == 0) return 1;
                return 0;
            }
            int count = 0;
            count += helper(nums, target + nums[pos], pos + 1);
            count += helper(nums, target - nums[pos], pos + 1);
            return count;
        }
    }
    

  • 0
    W

    This is very helpful and understandable! Thanks


  • 0
    X

    definitely this method can be optimized by adding a map to get the number of target value can be obtained at pos.


Log in to reply
 

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