Number of ways to make change for an amount

Task

Write a program that, given the amount to make change for and a list of coins prints out how many different ways you can make change from the coins to STDOUT.

My approach

The number to make change for is N. Take one coin C and sum the number of ways to make N - C with the other coins. Add the number of ways to make N - 2C with the other coins, etc, for all N - XC > 0 where X is the number of C coins used. Do that recursively. Memoize it so it's effectively dynamic programming.

Code

(ns hackerrank.core
  (:require [clojure.string :as string]))

(defn get-ways
  [n coins]
  (if (= n 0)
    1
    (if (= (count coins) 0)
      0
      (let [[coin & other-coins] coins]
        (reduce
          #(+ %1 (get-ways (- n (* coin %2)) other-coins))
          (if (= (mod n coin) 0) 1 0)
          (range 0 (/ n coin)))))))

(def get-ways-memoized
  (with-redefs [get-ways (memoize get-ways)] get-ways))

(let
  [n (Integer/parseInt (nth (string/split (read-line) #"\s+") 0))
   coins-line (read-line)
   coins (if (= "" coins-line)
           []
           (map #(Integer/parseInt %) (string/split coins-line #" ")))]
  (println (get-ways-memoized n coins)))

Questions

-
Any Clojure style / best practices, I'm mostly doing this to learn Clojure.

-
Any ideas why this wouldn't pass the timing tests on HackerRank. I've checked that the memoized function runs faster than the non-memoized one and AFAIK apart from the large stack resulting from no tail call optimization it should be equivalent to an iterative approach with a matrix storing the results.

-
Is there a way to do this manually, bottom-up rather than using memoize? Pseudo-code or a hint would be great as I'd like to try to implement it myself. Intuitively it feels like there can't be a bottom-up approach because I don't know in advance which sub-problems need to be solved.

Any Clojure style / best practices

Your nested if statements in get-ways might be nicer as a cond:

(defn get-ways
  [n coins]
  (cond
    (= n 0) 1
    (= 0 (count coins)) 0
    :else (let ...)))

There may be other things, but I'm not a clojure pro.

Why it won't pass the timing tests on HackerRank.

I suspect your with-redefs isn't doing what you expect. with-redefs will redefine get-ways for the duration of the with-redefs block. But all you're doing in that block is returning the re-defd function. So your initial call will call the memoized function, but every recursive call just calls the orignal function, so you lose all the benefit of memoizing in the first place.

You may be better off wrapping your (println (get-ways-memoized n coins))) in with-redefs, or maybe just redfining get-ways to always be memoized:

(def get-ways 
  (memoize (fn
    [n coins]
    ...)

Is there a way to do this manually.

Not sure, I'll leave that to someone else to try and answer.

StackExchange Code Review Q#125032, answer score: 2