change, R - rextester

Language: Layout:

change <- function(target, coins, condition, numCoins) {
  # Finds all combinations of coins to equal the target value while using the condition number of coins.
  solutions <- c()
  
  for (h in 1:max(numCoins, length(coins))) {
    # Start by considering h = 1, 2, 3, ... coins.
    combinations <- combn(coins, h)
    solutions <- c(solutions, sapply(1:ncol(combinations), function(colIndex) {
      combination <- combinations[,colIndex]
      total <- sum(combination)
      solution <- NA
      
      if (condition == '<') {
        if (total == target && h < numCoins) {
          solution <- combination
        }
      }
      else if (condition == '<=') {
        if (total == target && h <= numCoins) {
          solution <- combination
        }
      }
      else if (condition == '==') {
        if (total == target && h == numCoins) {
          solution <- combination
        }
      }
      else if (condition == '>') {
        if (total == target && h > numCoins) {
          solution <- combination
        }
      }
      else if (condition == '>=') {
        if (total == target && h >= numCoins) {
          solution <- combination
        }
      }

solution
    }))
  }
  
  # Remove NAs from solution
  solutions <- unique(solutions[!is.na(solutions)])
  if (length(solutions) == 0) {
    NA
  }
  else {
    solutions
  }
}

# Run test cases.
inputs <- list(
  list(target=10, coins=c(5, 5, 2, 2, 1), condition='<=', n=3),
  list(target=150, coins=c(100, 50, 50, 50, 50), condition='<', n=5),
  list(target=130, coins=c(100, 20, 18, 12, 5, 5), condition='<', n=6),
  list(target=200, coins=c(50, 50, 20, 20, 10), condition='>=', n=5)
)

sapply(inputs, function(input) {
  print(paste('== Target', input$target, '=='))
  print(change(input$target, input$coins, input$condition, input$n))
})

[ + ] Show input
Absolute running time: 0.58 sec, cpu time: 0.7 sec, memory peak: 30 Mb, absolute service time: 0,6 sec