LeetCode 494: Target Sum

Explanation:

To solve this problem, we can use a recursive approach where we consider each element in the given array nums and decide whether to add it with a positive or negative sign. We can keep track of the current sum and the index of the element we are currently considering. The base case for the recursion is when we reach the end of the array, at which point we check if the current sum equals the target.

We can create a recursive function calculateWays that takes parameters nums, target, sum, and index. Within this function, we make two recursive calls for each element in nums: one by adding the element with a positive sign and the other by adding the element with a negative sign. We continue this process until we reach the end of the array.

The time complexity of this approach is O(2^n) where n is the number of elements in the array nums. The space complexity is O(n) for the recursive call stack.

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        return calculateWays(nums, target, 0, 0);
    }
    
    private int calculateWays(int[] nums, int target, int sum, int index) {
        if (index == nums.length) {
            return sum == target ? 1 : 0;
        }
        
        int ways = 0;
        ways += calculateWays(nums, target, sum + nums[index], index + 1);
        ways += calculateWays(nums, target, sum - nums[index], index + 1);
        
        return ways;
    }
}