Recursive solution for Coin Sum DP Problem

coinSumDPRecursive.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, make(map[string]int)))
}

func CoinSum(sum int, index int, memory map[string]int) (result int) {
	if index >= len(denoms) || sum > target {
		return 0
	} else if sum == target {
		return 1
	}
	key := fmt.Sprint(sum, index)
	if result, ok := memory[key]; ok {
		return result
	}
	result += CoinSum(sum+denoms[index], index, memory)
	result += CoinSum(sum, index+1, memory)
	memory[key] = result
	return
}