from fractions import Fraction

# 第五章 作业一
# 有分数1/2，1/3，1/4，1/5，1/6，1/8，1/10，1/12，1/15，求将其中若干个分数相加和恰好等于1的组成方案，并输出
#
# 1. 给定的分数使用 Fraction 类型，可以方便地进行分数的计算和比较。
#
# 2. 使用递归来查找满足条件的组合。参数：
#    - `target`：目标和，初始值为 1。
#    - `current_combination`：当前已选择的分数组合，初始为空列表。
#    - `index`：当前处理的分数在列表中的索引，初始为 0。
#
# 3. 在递归函数中，有两个选择：
#    - 不选择当前分数：继续递归，不修改 `target` 和 `current_combination`。
#    - 选择当前分数：继续递归，更新 `target` 为 `target - fractions[index]`，并将当前分数添加到 `current_combination` 中。
#
# 4. 当 `target` 等于 0 时，我们找到了一个满足条件的组合，将其打印出来。
#
# 5. 递归继续处理下一个分数，直到遍历完所有分数或找到所有满足条件的组合。


def find_combinations(
    target: Fraction,
    fractions: list[Fraction],
    current_combination: list[Fraction],
    index: int,
    resultSet: list[list[Fraction]],
):
    if target == 0:
        resultSet.append(current_combination.copy())
        return
    if index >= len(fractions):
        return

    # 不选择当前分数
    find_combinations(target, fractions, current_combination, index + 1, resultSet)
    # 选择当前分数
    find_combinations(
        target - fractions[index],
        fractions,
        current_combination + [fractions[index]],
        index + 1,
        resultSet,
    )


fractions = [
    Fraction(1, 2),
    Fraction(1, 3),
    Fraction(1, 4),
    Fraction(1, 5),
    Fraction(1, 6),
    Fraction(1, 8),
    Fraction(1, 10),
    Fraction(1, 12),
    Fraction(1, 15),
]

result_set = []

find_combinations(
    target=1, fractions=fractions, current_combination=[], index=0, resultSet=result_set
)

for result in result_set:
    print(" + ".join(map(str, result)) + " = 1")