Coin Change Algorithm - coding challenge Recently I came across a coding problem where I have to find the least positive value which is not possible to make using the coins present in the coin denomination array(array values can be used only once).
suppose that

if the input is 3 5 7, the answer is 1

if the input is 1 2 4, the answer is 8

if the input is 1 3 4, the answer is 2

I have written a solution using recursion but it has a time complexity of \$O(n!)\$.
It is given that the size of the array cannot be greater than 25 and no individual value being greater than 100,000.

    public class Test {
        public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            int coins = scan.nextByte(); // max 25
            int maxPossible = 0;
            Integer[] coinsDenominationarray = new Integer[coins];
            for (int i = 0; i &lt; coins; i++) {
                coinsDenominationarray[i] = scan.nextInt(); // max 1,00,000
                maxPossible += coinsDenominationarray[i];
            }
            Arrays.sort(coinsDenominationarray);
        /* 
         * +1 because the coins will not be able to make 1 more than sum of all the coins. 
         * Using this value for the upper limit for the for-loop. 
         * In case the recursion is not able to find any value not possible to make
           using any combination of coins. This will be the final answer.
        */
            System.out.println(solve(maxPossible+1, coinsDenominationarray));
        }

        public static int solve(Integer maxNotPossible, Integer[] arr) {
            for (int num = 1; num &lt; maxNotPossible; num++) {
                if (isPresent(num, arr)) {
                    continue;
                }
                if (!isPossible(num, 0, possibleDenominations(num, arr))) {
                    return num;
                }
            }
            return maxNotPossible;
        }

        public static boolean isPossible(int toMake, int sum, Integer[] arr) {
            if (toMake &lt; sum) {
                return false;
            }
            for (int num : arr) {
                int currentSum = sum + num;
                if (currentSum == toMake) {
                    return true;
                } else if (currentSum &gt; toMake) {
                    return false;
                } else if (isPossible(toMake, currentSum, removeAndReturn(num, arr))) {
                    return true;
                }
            }
            return false;
        }

        public static Integer[] removeAndReturn(Integer num, Integer[] arr) {
            List&lt;Integer&gt; list = new LinkedList&lt;Integer&gt;(Arrays.asList(arr));
            list.remove(num);
            return list.toArray(new Integer[list.size()]);
        }

        public static Integer[] possibleDenominations(Integer maxNum, Integer[] arr) {
            List&lt;Integer&gt; list = new ArrayList&lt;&gt;();
            for (int num : arr) {
                if (num &gt;= maxNum) {
                    break;
                }
                list.add(num);
            }
            return list.toArray(new Integer[list.size()]);
        }

        public static boolean isPresent(int num, Integer[] arr) {
            List&lt;Integer&gt; list = Arrays.asList(arr);
            return list.contains(num);
        }

    }


link to the original challenge:
https://www.techgig.com/challenge/IG_Graduate_Programme_2018

Unfortunately, this is not an open challenge.
I'll start with a review of your existing code, and then make a suggestion
for a better algorithm.

The first thing to notice is that there are many conversions from arrays
to lists and back to arrays:


In the isPresent() function, the array is converted to a list in order
to check if it contains a given number. But the array is already sorted,
so one can call Arrays.binarySearch instead, which is more also efficient.
The possibleDenominations function “truncates” the given array by conversion
to a list and back to an array.
You could compute the last index to be included instead and then return
a subarray with Arrays.copyOfRange. But I am not sure if this truncating
is needed at all, since your solution algorithm already early returns if 
the values become too large.
In the removeAndReturn function, the array is converted to a list
and back to an array in order to get a new array with the first element
removed.


All these conversions can be avoided completely: Either


keep the original array and pass indices (of the first and last
entry to be considered) around, or
store the values in an (Array)List right at the beginning, and use 
list.subList() to pass views of a portion of the list around, without
actually copying the elements.


The method


public static boolean isPossible(int toMake, int sum, Integer[] arr) {



can be simplified by taking a single parameter targetSum instead of
toMake and sum:

public static boolean isPossible(int targetSum, Integer[] arr) {
    if (targetSum == 0) {
        return true;
    } else if (targetSum &lt; 0) {
        return false;
    }
    for (int num : arr) {
        if (isPossible(targetSum - num, removeAndReturn(num, arr))) {
            return true;
        }
    }
    return false;
}


Further remarks:


“Test” is a non-descriptive name for a program. Why not name it after the
challenge, for example public class CoinChange? 
Why do you call nextByte() if the result is assigned to an int?
The variable name coins does not clearly indicate that this is the
number of coins.
coinsDenominationarray is an array, but there is no need to make the type
part of the variable name, I would call it for example coinDenominations or
coinValues.
Most of the code is done in a separate function, which is good. I would put
the calculation of maxPossible and the sorting into that function as well,
so that I/O and the actual computation are separated completely.
The parameter name arr in the solve function  is non-descriptive.
Why not use the same name as in the main program?
All methods (with the only exception of main) can be private.


Putting it all together, the program could look like this:

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.util.Collections;

public class CoinChange {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int numCoins = scan.nextInt();

        ArrayList&lt;Integer&gt; coinValues = new ArrayList&lt;Integer&gt;();
        for (int i = 0; i &lt; numCoins; i++) {
            coinValues.add(scan.nextInt());
        }
        int firstNotPossible = findFirstNotPossible(coinValues);
        System.out.println(firstNotPossible);
    }

    private static int findFirstNotPossible(List&lt;Integer&gt; coinValues) {
        Collections.sort(coinValues);

        // Compute sum of values plus one:
        int maxNotPossible = 1;
        for (int value : coinValues) {
            maxNotPossible += value;
        }

        for (int num = 1; num &lt; maxNotPossible; num++) {
            if (!coinValues.contains(num) &amp;&amp; !isSummable(num, coinValues)) {
                return num;
            }
        }
        return maxNotPossible;
    }

    // Check if `targetSum` is representable as a sum of numbers in `values`
    // (which is assumed to be a sorted list of positive numbers).
    private static boolean isSummable(int targetSum, List&lt;Integer&gt; values) {
        if (targetSum == 0) {
            return true;
        } else if (targetSum &lt; 0) {
            return false;
        }
        for (int i = 0; i &lt; values.size(); i += 1) {
            if (isSummable(targetSum - values.get(i), values.subList(i + 1, values.size()))) {
                return true;
            }
        }
        return false;
    }
}


A better algorithm

Your isPossible() function solves the "Subset sum problem"
with “brute force,” i.e. by (recursively) trying all possible combinations.

This problem can be efficiently solved with "dynamic programming", as described in
the Wikipedia article.

But this problem can be solved even simpler: 


A number \$ N \$  stores the lowest value which is not
representable as sum of coin values considered so far, initially \$ N = 1 \$.
For all values \$ v \$ in the (sorted) array of coin values:


If \$ v &gt; N \$ then we are done, \$ N \$ is not representable.
Otherwise \$ N \$ is incremented by \$ v \$.



This requires only a single traversal of the array, and no additional storage:

import java.util.Scanner;
import java.util.Arrays;

public class CoinChange {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int numCoins = scan.nextInt();

        int[] coinValues = new int[numCoins];
        for (int i = 0; i &lt; numCoins; i++) {
            coinValues[i] = scan.nextInt();
        }
        int firstNotPossible = findFirstNotPossible(coinValues);
        System.out.println(firstNotPossible);
    }

    private static int findFirstNotPossible(int[] coinValues) {
        Arrays.sort(coinValues);

        int firstNotPossible = 1;
        for (Integer value : coinValues) {
            if (value &gt; firstNotPossible) {
                break;
            }
            firstNotPossible += value; 
        }
        return firstNotPossible;
    }
}