Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement