Simple dfs solution.

  • 2

    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.