find if given pack of coins can make a given value - coin row problem

Question

given array of coins (int) and an int n the function need to return true if there is atleast one solution to the coin-change problem. meaning: for array of ints> 0: [c(0) ,c(1) ,c(2) ,c(3) ,...... ,c(k)]. check if there is a solution for

the eqauation: a(0)*c(0)+ a(1)*c(1)+.....+ a(k)*c(k)= n. //n is the money we need to change

given c(0),c(1),....,c(n) >0 and a(0),a(1),....,a(n) =>0 both integers.

---

so I managed to make this code: the problem is that its algorithmic efficiency sucks, and this should be running on high values, and big coins array, so I need a code that is able to do this quicker.

public static boolean change(int[] coins, int n) {
  boolean ans = false;
  //loop running in recursion till founds ans/ passing limit
  for (int i = 0; i < coins.length & (!ans); i = i + 1) {
    if (n % coins[i] == 0) {
      return true;
    }
    if (n >= coins[i]) {
      ans = change(coins, n - coins[i]);
    }
  }
  return ans;
}//O(n*k^n) solution for false ans , very bad :(

• for example: for coins = {2,4,8} and n= 4111; I should get false, but the program unable to run this.

btw I would prefer this function to use recursion, but any solution/ guidnes is good :)

---

this is an other try doing this better but still not running as wanted. //trying to use binary search and using divisions instead of minus

---

    public static int iscashable(int[] coins, int n, int min, int max)
    {
        int check=(max+min)/2;
        if(check == coins.length-1 | check == 0)
            return check;
        if(n/coins[check] > n% coins[check])
        {
            return (iscashable(coins,n,check,max));
        }
        else
        {
            return check;
        }
    }
    public static int canchange(int[] coins, int n, int count)
    {
        int x=0;
        int check= iscashable(coins,n,0,coins.length-count);
        if(n%coins[check]==0)
        {
            return 0;
        }
        if(check==0)
        {
            return n;
        }
            if(n/coins[check] > n% coins[check])
            {
                x= (n/coins[check]) - (n% coins[check]);
                int k= n-(coins[check]*x);
                return canchange(coins, k, count+1);
            }
            else
            {
                return canchange(coins,n-coins[check],count+1);
            }
    }

• the problem is both about runtime and number of recursion calls (with big number given, every recursion layer is coins.length^(num of layers));

I really thank you for your help!