Given 1 coin from multiple denominations (E.G. a 1 coin, 5 coin, 16 coin), and a sum, return true or false determining if the sum can be made.

boolean go(int[] coins, int goal) 
{
  //Will set each time, but shouldn't matter as toggle is at bottom
  boolean ans = false;
   
  //loop running in recursion till founds ans
   
  //Really bad time complexity lol
  for (int i = 0; i < coins.length && (!ans); i  ) {
    if ((goal - coins[i] == 0) || goal == 0) {
      return true;
    }
     
    if (goal > coins[i]) {
      int[] red = new int[coins.length - 1];
      //it necessary because making list with one less
      int it = 0;
      //Setting new list to avoid runtime
      for(int x = 0; x < coins.length; x  ){
        if(!(i == x)){
          red[it] = coins[i];
          it  = 1;
        }
      }
      //Run with new list
      ans = go(red, goal - coins[i]);
    }
  }
  return ans;
}

This is my code so far. I have made it recursive, yet one of the test cases returns true when it should not. The test case in particular is [111, 1, 2, 3, 9, 11, 20, 30], with the goal doing 8; This should return false (as it cannot add up to 8), but in this case, returns true.

Other test cases work fine, so I believe my code has some sort of an exception.

I have tried to move the base case upward, and make a reverse variation...

boolean go(int[] coins, int goal) 
{
  boolean ans = false;
  if(goal == 0){
    return true;
  }else if(goal < 0){
    return false;
  }
  for (int i = 0; i < coins.length && (!ans); i  ) {
    if (goal >= coins[i]) {
      int[] red = new int[coins.length - 1];
      int it = 0;
      for(int x = 0; x < coins.length; x  ){
        if(!(i == x)){
          red[it] = coins[i];
          it  = 1;
        }
      }
      ans = go(red, goal - coins[i]);
    }
  }
  return ans;
}

is what I've tried, but the base case doesn't seem to affect anything

CodePudding user response：

The bug is in your copying of the coins array: red[it] = coins[i] should really be red[it] = coins[x]...

For time complexity, you don't really have to do a loop inside the method. Each denomination is either part of the sum or not, so you can always remove the first denomination and test with and without it:

boolean go(int[] coins, int goal)  {
    if(goal == 0)
        return true;
    else if(coins.length == 0 || goal < 0)
        return false;
    else {
        int[] tailOfCoins = Arrays.copyOfRange(coins, 1, coins.length);
        return go(tailOfCoins, goal) || go(tailOfCoins, goal - coins[0]);
    }
}