#494 Target Sum LeetCode question using Recusion with Memoization

Question

I came across the following question in LeetCode while studying stacks and I'm able to get the brute-force solution. There's a lot of videos + solutions on the DP method but I would like to understand the recursion with memoization method (since I'm not studying DP).

I thought that by maintaining the sum in calc(), I was keeping the previously computed results, which implies memoization... but I suppose that's not the case.

My current brute-force solution is

class Solution {
    private int count = 0;
    
    public int findTargetSumWays(int[] nums, int target) {
        calc(nums, target, 0, 0);
        return this.count;
    }
    
    private int calc(int[] nums, int target, int sum, int i) {
        if (i == nums.length) {
            if (sum == target) {
                count++;
            }
            return sum;
        }
        
        calc(nums, target, sum + nums[i], i+1);
        calc(nums, target, sum - nums[i], i+1);  
        
        return 0;
    }
}

The problem statement is:

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

• For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".

Return the number of different expressions that you can build, which evaluates to target.

Answer 1

This solution is Targer Sum problem from leetcode with recursive aaproach

 public int findTargetSumWays(int[] nums, int target) {
    return countTarget(nums, 0, 0, target);
}

public int countTarget(int[] nums, int pos, int sum, int target) {
    if (nums.length == pos) {
        return sum == target ? 1 : 0;
    }
    return countTarget(nums, pos + 1, sum + -nums[pos], target)
        + countTarget(nums, pos + 1, sum + nums[pos], target);
}