hello_samuel.rb

#!/usr/bin/env ruby

# https://twitter.com/smlpth/status/1693574834179961234
# "I have an array of amounts on one hand and a target amount on the other. I need to find a combination of amounts in the array that sums to the target. If multiple combinations work, take the one containing the most recent amounts."

require 'logger'

logger = Logger.new(STDOUT)
logger.level = :debug # set it to info to only see matches
# logger.level = :info

target_amount = 80
amounts = [
  100,
  20,
  50,
  40,
  10,
  60,
  25,
  70
].delete_if { |i| i > target_amount }

max_idx = amounts.count - 1

class Node
  attr_accessor :value, :total, :idx
  attr_accessor :parent_node, :children

  def initialize(parent_node:, value:, idx:)
    @parent_node = parent_node
    @value = value
    @idx = idx
    @children = []
  end

  def total
    return @total if defined?(@total)

    parent_total = parent_node.nil? ? 0 : parent_node.total
    @total = parent_total + value
  end

  def to_s
    return idx.to_s if parent_node.nil?

    [parent_node.to_s, idx.to_s].join("->")
  end
end

root = Node.new(parent_node: nil, value: amounts[0], idx: 0)
match = nil

incomplete_nodes = [root]

logger.debug "amounts = #{amounts}"

round = 1
while incomplete_nodes.any?
  logger.debug "* round ##{round} (incomplete_nodes.count = #{incomplete_nodes.count})"
  next_round = []
  incomplete_nodes.each do |node|
    logger.debug "    node.idx = #{node.idx} (value: #{node.value})"
    unless node.idx == max_idx
      ((node.idx + 1)..max_idx).to_a.each do |child_idx|
        child_node = Node.new(parent_node: node, value: amounts[child_idx], idx: child_idx)
        logger.debug "    child_idx = #{child_idx}/#{max_idx} (value: #{child_node.value}) total=#{child_node.total}"
        node.children << child_node

        if child_node.total == target_amount
          # I chose to keep the best match, but we can keep track of several ones if we need to perform post-filtering.
          # I'm thinking of something like a Sudoku: one cell (C1) might accept multiple good answers,
          # but other cells, with their own constraints, might later narrow down the list of good answers for C1.
          match = child_node if match.nil? || match.idx > child_node.idx
          logger.info "FOUND at #{child_node.to_s}"

          # From now on, no need to look further down the tree for a match,
          # we only need to look for a potential match with more "recent" amounts (idx closer to zero)
          max_idx = child_node.idx
        else
          next_round << child_node
        end

      end
    end
  end
  incomplete_nodes = next_round
  round += 1
end

if match.nil?
  logger.info "No match found."
else
  logger.info "Best match: #{match.to_s}"
end