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));
}
}