# 枝刈りを追加したPythonコード

import collections

# --- 初期データの設定 ---
numbers = [0, 10, 34, 55, 77]
n = 4
target = 100

class Status:
    def __init__(self, total=0, selected_numbers=None, next_index=1):
        self.total = total
        self.selectedNumbers = selected_numbers if selected_numbers else []
        self.nextIndex = next_index

def nextStatus1(s):
    new_total = s.total + numbers[s.nextIndex]
    new_selected = s.selectedNumbers + [numbers[s.nextIndex]]
    new_next_index = s.nextIndex + 1 if s.nextIndex < n else 0
    return Status(new_total, new_selected, new_next_index)

def nextStatus2(s):
    new_next_index = s.nextIndex + 1 if s.nextIndex < n else 0
    return Status(s.total, s.selectedNumbers, new_next_index)

def treeSearchWithPruning():
    ansStatus = None
    queue = collections.deque()

    currentStatus = Status()
    queue.append(currentStatus)

    while len(queue) != 0:
        currentStatus = queue.popleft()

        # --- 評価処理 ---
        if ansStatus is None:
            ansStatus = currentStatus
        elif abs(target - ansStatus.total) > abs(target - currentStatus.total):
            ansStatus = currentStatus

        # --- [図3] 探索回数の削減処理 ---
        # 合計が目標以上の場合は探索中止(N)、そうでなければ継続(Y)
        if currentStatus.total >= target:
            nextFlag = "N" # [オ]
        else:
            nextFlag = "Y" # [カ]

        # --- 次の状態の生成（条件を修正） ---
        # (β) 次の数があり、かつ nextFlag が "Y" である場合のみ分岐
        if currentStatus.nextIndex != 0 and nextFlag == "Y":
            queue.append(nextStatus1(currentStatus))
            queue.append(nextStatus2(currentStatus))

    return ansStatus

# 実行
result = treeSearchWithPruning()
print(f"【枝刈りあり】合計: {result.total}, 選択: {result.selectedNumbers}")