Coin sum problem solved recursively in exponential time.

coinSumExponentialRecursive.go

package main

import "fmt"

const target = 200

var denoms = [...]int{200, 100, 50, 20, 10, 5, 2, 1}

func main() {
	fmt.Println(CoinSum(0, 0))
}

func CoinSum(sum int, index int) (result int) {
	if index >= len(denoms) || sum > target {
		return 0
	} else if sum == target {
		return 1
	}

	result += CoinSum(sum+denoms[index], index)
	result += CoinSum(sum, index+1)

	return
}