educative.io

Educative

Recursive Approach Not Working

I am trying to use recursive method for this problem, where the result expected for the first input is 5. But I am getting 1 as output. Can you please clarify if my recursive solution is correct and if not can you please post a valid recursive solution ?

class TargetSum {

  public int findTargetSubsets(int[] nums, int s) {
    int sum = 0;
    for (int n : nums) {
      sum += n;
    }

    return countSubsets(nums, (s + sum) / 2, 0);
  }

  public int countSubsets(int[] nums, int sum, int currentIndex) {

    if (currentIndex >= nums.length || nums.length == 0) {
      return 0;
    }

    if (sum == 0) {
      return 1;
    }

    int sum1 = 0;
    if (nums[currentIndex] <= sum) {
      sum1 = countSubsets (nums, sum - nums[currentIndex], currentIndex + 1);
    }

    int sum2 = countSubsets(nums, sum, currentIndex + 1);

    return (sum1 + sum2);
  }
  
  public static void main(String[] args) {
    TargetSum ts = new TargetSum();
    int[] num = {1, 1, 1, 1, 1};
    System.out.println(ts.findTargetSubsets(num, 3));
    num = new int[]{1, 2, 7, 1};
    System.out.println(ts.findTargetSubsets(num, 9));
  }
}