已知n+1个正数：w i ​ (1<=i<=n)和M，要求找出{w i ​ }的所有子集使得子集中元素之和等于M。解采用可变长的k-元组(x 1 ​ ,...,x k ​ ) 表达，其中：x i ​ ∈{1, ..n}，表示被选中的数值w的下标，1<=i<=k。隐式约束条件是选中的数值和数为M，x i ​ 相互不同，且按取值从小到大顺序排列。 要求利用FIFO分支限界方法解决子集和数问题。 输入格式: 第一行为一个不超过200的正整数n，表示总集规模； 第二行是正整数M，表示子集的和数； 第三行是总集中n个正整数，中间用空格隔开。 输出格式: 如果有答案，则输出所有满足条件的子集（用可变长度数组表示符合条件的一个子集，子集中元素表示被选中的数值的下标）； 如果没有答案，则输出“no solution!”。

为了方便理解，我先解释一下FIFO分支限界算法的基本思路。FIFO分支限界算法是一种广度优先搜索算法，它的基本思路是：将搜索树的节点放入一个队列中，每次从队列中取出队首元素扩展子节点，并将子节点加入队列末尾，然后按照某种规则排序队列，使得优先级高的节点优先扩展。

接下来，我们按照题目要求，使用FIFO分支限界算法求解子集和问题。首先，读入输入数据：

n = int(input())  # 集合大小
M = int(input())  # 目标和
w = list(map(int, input().split()))  # 集合中的数

接着，定义一个节点类，用于表示搜索树的节点。每个节点包含以下属性：

- `path`：表示节点对应的可行解。
- `bound`：表示节点的上界，用于排序和剪枝。
- `level`：表示节点在搜索树中的深度。

class Node:
    def __init__(self, path, bound, level):
        self.path = path
        self.bound = bound
        self.level = level

接下来，定义一个计算上界的函数`bound()`。该函数用于计算当前节点的上界，用于排序和剪枝。具体计算方法如下：

1. 计算当前节点已选数的和`cur_sum`。
2. 计算剩余数的和`rem_sum`，即从当前节点所在层往下所有数的和。
3. 如果`cur_sum`已经超过了目标和`M`，则返回负无穷；如果`cur_sum`加上`rem_sum`仍然小于`M`，则返回当前节点的和作为上界；否则，返回当前节点的和加上剩余数的平均值作为上界。

def bound(path, w, M):
    cur_sum = sum(w[i-1] for i in path)
    rem_sum = sum(w[i-1] for i in range(path[-1]+1, len(w)+1))
    if cur_sum > M:
        return float('-inf')
    elif cur_sum == M:
        return cur_sum
    else:
        return cur_sum + (rem_sum / len(w[path[-1]:]))

接下来，定义搜索函数`subset_sum()`，该函数使用FIFO分支限界算法搜索所有满足条件的子集。具体步骤如下：

1. 将根节点加入队列，并初始化最优解和最优路径。
2. 循环执行以下操作，直到队列为空：
1. 取出队首元素。
2. 如果当前节点的上界小于当前已知最优解，则剪枝，直接跳过。
3. 如果当前节点的和等于目标和，将当前节点的可行解加入结果集，并更新最优解和最优路径。
4. 否则，生成当前节点的所有子节点，并计算它们的上界，将子节点加入队列，并按照上界从小到大排序。
3. 返回结果集和最优路径。

def subset_sum(w, M):
    # 初始化根节点
    root = Node([], bound([], w, M), 0)
    queue = [root]  # 初始化队列
    result = []  # 初始化结果集
    best_path = []  # 初始化最优路径
    best_bound = float('-inf')  # 初始化最优上界

    while queue:
        node = queue.pop(0)

        # 剪枝
        if node.bound <= best_bound:
            continue

        # 找到一个可行解
        if sum(w[i-1] for i in node.path) == M:
            result.append(node.path)
            if not best_path or len(node.path) < len(best_path):
                best_path = node.path
                best_bound = len(best_path)
        
        # 扩展子节点
        for i in range(node.level+1, len(w)+1):
            child_path = node.path + [i]
            child_bound = bound(child_path, w, M)
            if child_bound > best_bound:
                queue.append(Node(child_path, child_bound, node.level+1))
                queue.sort(key=lambda x: x.bound)

    if result:
        print(result)
    else:
        print("no solution!")

最后，调用`subset_sum()`函数进行搜索，并输出结果：

subset_sum(w, M)

完整代码如下：