# 部分和問題　Pythonによる実装例
import collections

# --- 初期データの設定（例：10, 34, 55, 77 の中から目標 100 に近いものを探す） ---
numbers = [0, 10, 34, 55, 77]  # 配列の添字は1から始まるため、0番目はダミー
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 treeSearch():
    ansStatus = None  # 解答の候補
    queue = collections.deque()

    # 初期状態(A)を作成し、キューに格納する
    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

        # --- 次の状態の生成と格納 ---
        if currentStatus.nextIndex != 0: # [エ]：次の数がある場合
            # 次の数を選択した状態をキューに追加
            queue.append(nextStatus1(currentStatus))
            # 次の数を選択しない状態をキューに追加
            queue.append(nextStatus2(currentStatus))

    return ansStatus

# 実行
result = treeSearch()
print(f"目標: {target}")
print(f"合計: {result.total}")
print(f"選択した数: {result.selectedNumbers}")