RECURSION | DYNAMIC PROGRAMMING | SUBSET SUM PROBLEM | INTERVIEW | CLEAN CODE

def subset_sum(arr, sum)
  return true if arr.size == 0 and sum == 0 
  
  # arr.sort!
  
  buffer = Array.new(arr.size+1){Array.new(sum+1, false)}
  
  (0..arr.size-1).each do |i|
    buffer[i][0] = true 
  end 
  
  buffer[0][0] = true 
  
  #p buffer
  
  (1..arr.size).each do |i|
    (0..sum).each do |j|
      
      if j < arr[i-1]
        buffer[i][j] = true if buffer[i-1][j] 
      else 
         buffer[i][j] = true if buffer[i-1][j] or buffer[i-1][j-arr[i-1]]
      end 
    end 
  end
  
  return buffer[-1][-1]


end 

subset_sum([2,3,8,9,10], 111)