infinitilab algo question

find_target_combination.py

# python3

from collections import deque

# Store combinations as a tree. The size of the tree directly
# corresponds to the running time of the algorithm - O(2^n)
# Worst runtime is when the sum of items is larger than the target
# and no combination exist. An intuitive optimization here is to
# prune combinations away when the sum has already exceeded the target
class Node:
    def __init__(self, val, total):
        self.parent = None
        self.val = val
        self.total = total

    def branch(self, val, total):
        nod = Node(val, total)
        nod.parent = self
        return nod

# return array of indices of elements that sum to total. Instead of an
# exhaustive search, the algorithm returns the first match it finds
def find_target_combination(items, target):
    # Good to shortcut our efforts if possible:
    s = sum(items)
    if s == target:
        return items
    elif s < target:
        return []

    q = deque()
    n = len(items)

    # Initial population of root nodes
    for i in range(len(items)):
        total = items[i]
        if total == target:
            return [i]
        elif total < target:
            q.append(Node(i, total))

    while True:
        if len(q) == 0:
            break

        nod = q.popleft()
        total = nod.total
        last = nod.val
        for i in range(last + 1, n):
            s = total + items[i]
            if s == target:
                # Leaf -> root to find indices; it is guaranteed
                # indices will be in desc order
                idxs = [i]
                while nod is not None:
                    idxs.append(nod.val)
                    nod = nod.parent
                return idxs
            elif s < target:
                q.append(nod.branch(i, s))
    
    return []
    

print(find_target_combination([10, 20, 10, 10, 5, 30, 70], 75))