First solution:
(defn groupSum [l x]
(or (zero? x) ; we have won!
(and (not (< x 0)) ; we can't win
(not (empty? l)) ; lost!
(or (groupSum (rest l) (- x (first l)))
(recur (rest l) x)))))
The "we can't win" line assume that all numbers are positive. We use
tail recursion in the only place we can use it.
If all numbers are positive, a more elaborate version would use this fact:
If all numbers are positive, and the sum of a suffix can't reach a
target, you should not try without the first element.
So the function will return :
- either 0 if we reach the goal
- a negative number if we went over the goal
- a positive number if we went under the goal.
If we went under the goal, we don't need to try without the first element.
(defn groupSum0 [l n]
(if (or (empty? l) (< n 0))
n
(let [res (groupSum0 (rest l) (- n (first l)))]
(if (>= res 0) res ;; we are either winning or can't reach
the goal
(if (zero? (groupSum0 (rest l) n))
0 ;; we have won
res))))) ;; we repeat we can
reach the goal from here
(defn groupSum [l n] (zero? (groupSum0 l n)))
Next step would be to make groupSum0 not stack overflow on big inputs
and to add memoization to it.
Best regards,
Nicolas.
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
