Coding bat problem: codingbat.com/prob/p145416 Recursion groupSum given an array of ints, is it possible to choose a group of some of the ints so that the group sums to the given target the convention is to use a starting index so the form is fn(start int-array target) examples fn(0 [2 4 8] 10) -> true since 8+2 = 10 fn(0 [2 4 8] 9) -> false sin…

group-sum-kata.clj

(defn group-sum [start nums target]
  (cond (>= start (count nums)) (= target 0)
        (or (group-sum (inc start) nums (- target (nth nums start)))
            (group-sum (inc start) nums target))
         true
         :else false))

;;first condition we check for is if the starting index is greater than or equal to the number of elements.
;; the only time that is true is if the target is 0
;; next we call our function with the index increased subtracting the element at the start index from our target 
;; if it returns true we short circuit to true, else we eval our function again with the start value increased and everything else 
;; the same
;;if that returns true the or statement passes true to the cond statement which returns true
;;else cond gets false

;;(group-sum 0 [2 4 8] 10) => true
;;(group-sum 1 [2 4 8] 2) => false

;;UPDATE: this is a direct translation from the java version.  working towards cleaning it up even more like this (thanks to xeqi in #clojure irc)...

(any? #(= (sum %) target) (sublists (drop start lst)))

GroupSumKata.java

...
//omitted the ceremony code for declaring this a java class with a main method that creates a new object just to call one method


public boolean groupSum(int start, int[] nums, int target) {
  // Base case: if there are no numbers left, then there is a
  // solution only if target is 0.
  if (start >= nums.length) return (target == 0);
  
  // Key idea: nums[start] is chosen or it is not.
  // Deal with nums[start], letting recursion
  // deal with all the rest of the array.
  
  // Recursive call trying the case that nums[start] is chosen --
  // subtract it from target in the call.
  if (groupSum(start + 1, nums, target - nums[start])) return true;
  
  // Recursive call trying the case that nums[start] is not chosen.
  if (groupSum(start + 1, nums, target)) return true;
  
  // If neither of the above worked, it's not possible.
  return false;
}