Divide a target sum into coins.

coins.R

# compute the different ways can you express tgt as the sum of a bunch of coins
# no greater than maxcoin. assume coins sorted in descending order,
# probably does not work great if there is no penny, or negative coins,
# or negative tgt.
coinrep <- function(tgt,coins=c(25,10,5,1),maxcoin=coins[1]) {
	stopifnot(tgt >= 0)
	stopifnot(all(diff(coins) < 0))   # reverse sorted.
	freecoins <- (coins <= min(maxcoin,tgt))
	basev <- rep(0,length(coins))
	if (! any(freecoins)) {
		retv <- list(basev)
	} else if (length(which(freecoins)) == 1) {
		basev[length(coins)] <- floor(tgt / coins[length(coins)])
		retv <- list(basev)
	} else {
		# for each coin less than maxcoin
		retv <- sapply(coins[freecoins],function(altc) {
			tailv <- coinrep(tgt - altc,coins=coins,maxcoin=altc)
			isme <- coins == altc
			tailv <- lapply(tailv,function(arep) {
				arep[isme] <- 1 + arep[isme]
				arep
			})
			tailv
		})
		# collapse
		if (!is.numeric(retv[[1]])) {
			retv <- unlist(retv,recursive=FALSE)
		}
	}
	retv
}
coinrep(3)
coinrep(17)
coinrep(53)