Answers for "Backtracking solution in ruby"

Backtracking solution in ruby

# the algorithm start
[1, 2, 3, 4, 5]12
# check for the first condition : 12-1 is not less than 0 so we subtract it from the sum
[2, 3, 4, 5]11
# check again 11-2 > 0 is true so we proceed
[3, 4, 5]9
# same thing here
[4, 5]6
# here 2-5 will return false so we go back to the parent call([4,5]6) and try to exclude the first case without touching the sum
[5]2
# we still get false because the array will be empty and the sum will be 1 so go back to the ancestor call([3,4,5]9)and exclude the first element without touching the sum
[5]6
# 9-4 > 0 is true so we proceed
[4, 5]9
# 5-5 is 0 so we return true
[5]5
true

Backtracking solution in ruby

def exact_sum?(sum, arr)
return true if sum==0
return false if sum < 0 || arr.empty?
# now we are checking both cases
exact_sum?(sum - arr[0], arr[1,arr.length]) || exact_sum?(sum, arr[1,arr.length])
end

puts exact_sum?(12, [1, 2, 3, 4, 5]);
# => true