如何设计算法找到数组A中累加和为B的最短可复用元素序列？

刚好之前碰到过类似的面试题，这题本质是个最短路径问题——把每个累加和看作图中的节点，从0出发，每一步加上A中的元素就是走一条边，我们要找从0到B的最短路径，对应的路径节点就是序列元素。

问题明确 #

给定自然数B和长度为n的数组A（A中元素均为互不相同的自然数），设计算法找出可重复使用A中元素、累加和恰好为B的最短序列。
示例：B=19，A=[4,5,7]，最短序列是[7,7,5]（或其他顺序的同长度组合），长度为3。

核心思路 #

BFS的层级遍历特性完美适配这个需求：每一层对应序列的长度，第一次到达B所在的节点时，对应的序列就是最短的。同时我们需要记录已经访问过的累加和，避免重复计算（比如已经通过4+5得到9，就不用再通过5+4重复处理9了，因为前者的序列长度和后者一样，再处理只会浪费资源）。

具体实现步骤 #

1. 先把数组A按从大到小排序（可选但推荐，能让大元素优先被尝试，大概率更快找到最短序列，减少队列压力）
2. 初始化队列，每个队列元素保存(当前累加和, 当前序列)，初始时队列里是(0, [])
3. 初始化一个访问集合，把0加进去，避免重复处理同一个累加和
4. 循环处理队列：
   • 取出队列头部的元素，判断当前累加和是否等于B，是则直接返回当前序列
   • 如果当前累加和小于B，遍历A中的每个元素，计算新的累加和
   • 若新的累加和不超过B且没被访问过，就把它加入访问集合，同时把(新累加和, 当前序列+[元素])加入队列
5. 如果队列遍历完都没找到等于B的累加和，说明无法组成B，返回None

Python代码示例 #

def find_shortest_sequence(target, nums):
    # 降序排序，优先尝试大元素，加速找到最短序列
    sorted_nums = sorted(nums, reverse=True)
    from collections import deque
    
    # 队列元素：(当前累加和, 当前序列)
    queue = deque([(0, [])])
    visited = set([0])
    
    while queue:
        current_sum, current_seq = queue.popleft()
        
        if current_sum == target:
            return current_seq
        
        for num in sorted_nums:
            new_sum = current_sum + num
            # 超过目标就跳过，避免无效计算
            if new_sum > target:
                continue
            if new_sum not in visited:
                visited.add(new_sum)
                queue.append((new_sum, current_seq + [num]))
    
    # 无法组成目标和的情况
    return None

# 测试示例
print(find_shortest_sequence(19, [4,5,7]))  # 输出类似 [7,7,5]

边界情况说明 #

• 如果A中存在元素等于B，那么最短序列就是[该元素]，长度为1，代码会直接返回
• 如果无法组成B（比如A全是偶数但B是奇数，或者A中所有元素都大于B），代码返回None
• 因为A中的元素都是自然数，不用担心负数导致的无限循环问题

内容的提问来源于stack exchange，提问作者John Lexus