Question

Write a recursive function that takes a start index, array of integers, and a target sum. Your goal is to find whether a subset of the array of integers adds up to the target sum. The start index is initially 0. A target sum of 0 is true for any array.

Answer 1

Here is the recursive function:

public static boolean subsetSum(int start, int[] nums, int target)

Step-by-step 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]) } //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.