Fork me on GitHub

Complexity for the toys solution is not n, as you call clojure sort in your code


case and compare might help you make the cond faster and/or more readable. Also, clojure.core already has memoize. And finally, rem is a simpler (slightly faster) form of mod, when you don't care about negative numbers:

(defn step-perms [n]
  (let [memoed
           (fn f [n]
            (case (compare n 3)
              -1 n
              0 4
              (+ (f (dec n))
                 (f (- n 2))
                 (f (- n 3))))))]
    (rem (memoed n) 10000000007)))
That being said, if you want peak performance, you'd want to preallocate a buffer for the "memoized" state, and compute it bottom-up. Looks like this:
(defn step-perms [n]
  (case (compare n 3)
    -1 n
    0 4
    (let [buf (int-array (inc n))
          _ (aset buf 1 1)
          _ (aset buf 2 2)
          _ (aset buf 3 4)]
      (loop [i 4]
        (if (> i n)
          (aget buf n)
            (aset buf i
                (+ (aget buf (dec i))
                   (aget buf (- i 2))
                   (aget buf (- i 3)))
            (recur (inc i)))))))
PS: haven't run these on Hackerrank