Answer:
Here is the recursive function:
public static boolean subsetSum(int start, int[] nums, int target) { //method definition
if (start >= nums.length) //base case
return (target == 0);
if(subsetSum(start + 1, nums, target - nums[start]) || subsetSum(start + 1, nums, target)) //recursive case
return true;
return false; }
Explanation:
Here is the complete program to test the working of the above method:
public class Main { //class name
public static void main(String[] args) { //start of main method
int[] nums = {2, 4, 8}; //creates and initializes array
System.out.println(subsetSum(0,nums,10)); } //calls method by passing start index i.e. 0, nums array and 10 is target sum
public static boolean subsetSum(int start, int[] nums, int target) { //method that takes start index, integer array and target sum as parameters
if (start >= nums.length) //if start index is greater than or equals to length of the array (base case)
return (target == 0); //returns target == 0
if(subsetSum(start + 1, nums, target - nums[start]) || subsetSum(start + 1, nums, target)) //recursive case to find whether a subset of the array of integers adds up to the target sum
return true; //returns true if the above condition is true
return false; } } //returns false if above condition is false
I will explain the program with the help of an example:
Lets say the num array has elements: 2,4 and 8. The method subsetSum works as follows:
Here start = 0
nums[] = {2,4,8}
target = 10
if (start >= nums.length) becomes:
if (0>= 3) this statement is false so the program moves to the recursive part:
if(subsetSum(start + 1, nums, target - nums[start]) || subsetSum(start + 1, nums, target)) this becomes:
if(subsetSum(0+ 1, {2,4,8}, 10 - nums[0]) || subsetSum(0+ 1, {2,4,8}, 10))
if(subsetSum(1, {2,4,8}, 10 - 2) || subsetSum(1, {2,4,8}, 10))
if(subsetSum(1, {2,4,8}, 8) || subsetSum(1, {2,4,8}, 10))
Now this method calls itself recursively to find whether a subset of the array nums adds up to 10.
The above recursive condition evaluates to true so the function returns true. The screenshot of program and its output is attached.
