Programming language is JAVA:
We have a set of coins of arbitrary positive values and want to see whether a given nonnegative total can be made using a some subset of the coins.
For example if we have two pennies, a nickel, two dimes and one quarter then the total 27 could be made using a quarter and two pennies (or alternatively two dimes, one nickel and two pennies).
On the other hand, given the same set of coins, we couldn't make the total 28 since we would need three pennies to add to the quarter and we only have two.
Implement a recursive function static boolean coinsMake(int [] coins, int startIndex, int total) that returns true if and only if the total can be made by adding a subset of the values in the coins array , from indexes startIndex to the last index (i.e. coins.length-1).
You function will need two base cases: When the total is zero and when startIndex reaches coins.length but the total is positive.
If the total is zero then we will always return true since 0 by convention can be made without needing any coins at all.
If the total is positive but startIndex is equal to coins.length, we will return false since in this case there are no values available to add.
The recursive case is when the total is greater than zero and startIndex is still less than coins.length.
In this case we will need to combine two recursive calls and return true if either of those calls returns true .
To figure out what the the two recursive calls are, think about two possibilities: either we use the coin at index startIndex or we don't.
As a precondition you can assume that both total and startIndex are nonnegative.
We would usually call coinsMake with startIndex equal to 0, since we want to know whether the total can be make using any subset of the coins, not just subsets that exclude the elements at indexes 0 through startIndex-1.
As an extra challenge, see if you can implement the method using a single line of code in the body, i.e. just a return statement which uses the logical operators && and ||.
For testing purposes, some coins will have values other than 1, 5, 10 etc. There is a coin worth 38 cents, for example.