Backtracking algorithm

phyton

e = [60, 60, 60, 60, 60, 45, 45, 45, 45, 45, 45, 30, 30, 30, 30, 30, 30, 30, 5]

def bt(data, limit, m=[]):
    data_sum = sum(m)
    print(m)
    # solution found
    if data_sum == limit:
        return (data, m)
    # we passed the limit, so no need to check further
    elif data_sum > limit:
        return False
    # data sum is < limit, so we keep looking...
    else:
        for i in range(len(data)):
            # clone the data and recurse
            data_ = data[:]
            m_ = m[:]
            m_.append(data_.pop(i))

            r = bt(data_, limit,  m_)
            if r:
                return r
        return False

res = bt(e, 330)
print(res)
print(sum(res[0]), sum(res[1]))

ruby

e = [60, 60, 60, 60, 60, 45, 45, 45, 45, 45, 45, 30, 30, 30, 30, 30, 30, 30, 5]

class Backtracking
  def self.bt(data, limit, m=[])
    data_sum = m.reduce(:+) || 0
    puts "m: #{m}"
    
    if data_sum == limit
      return [data, m]
    elsif data_sum > limit
      return false
    else
      data.each_with_index do |el, i|
        data_ = data.compact
        m_ = m.clone
        p m_
        m_ << data_.delete_at(i)
        result = self.bt(data_, limit, m_)
        
        return result if result
      end
      
      return false
    end
  end
end
res = Backtracking.bt(e,360)