从含零的99元素数组中寻找目标和的最优组合方案

核心前提 #

先明确几个关键定义：

• 「最小元素组合」：优先指元素个数最少，若个数相同则取元素值总和最小（常规场景下个数优先是核心需求）。
• 数组含零：零仅能作为补充项（加零不会改变和，但会增加元素个数），因此找最小组合时零无需主动纳入计算，仅当目标值为零时直接返回[0]即可。

从2元素到5+元素的通用最优策略 #

既然你已经掌握2元素的解法，针对5个及以上元素的场景，核心思路是从最少元素数开始逐层尝试，一旦找到解就停止——因为我们要的是最小组合，没必要继续尝试更多元素的情况。

1. 预处理数组 #

先做3步预处理，大幅降低后续计算量：

• 去重：保留每个唯一值即可，重复元素不会产生新的有效组合。
• 排序：按升序排列，方便后续剪枝和快速查找。
• 分离零与非零元素：零单独存放，后续仅在特殊场景（如目标值为零）使用，非零元素是核心计算对象。

2. 逐层尝试元素个数 #

从元素数1开始，依次尝试元素数2、3…直到找到解：

• 元素数1：直接检查目标值是否存在于数组中，存在则直接返回该单元素。
• 元素数2：用你熟悉的双指针法或哈希表法快速匹配，不多赘述。
• 元素数k（k≥3）：
  • 优先用动态规划（DP）：
    • 定义dp[s]为凑出和s所需的最少元素个数，初始化dp[0] = 0，其余为无穷大。
    • 遍历每个非零元素num，倒序遍历从num到目标值的所有和s，更新dp[s] = min(dp[s], dp[s-num] + 1)。
    • 若dp[target]不为无穷大，说明存在解，再通过回溯法找出具体的组合元素。
  • 回溯剪枝作为备选：
    • 排序后，若当前元素加上已选元素的和超过目标值，直接跳过后续更大元素。
    • 若当前元素与前一个元素相同，跳过（避免重复组合）。
    • 一旦找到某个元素数的解，立即停止更高元素数的尝试。

3. 目标值递增逻辑 #

如果当前目标值quota找不到任何组合，就将quota加1，重复上述逐层尝试的流程，直到找到首个可行的目标值及对应的最小组合。

关键优化点 #

• 提前获取数组最小正元素：如果目标值远大于数组元素，最终的最小组合大概率是多个最小正元素的累加（比如目标值为100，最小正元素是2，那最小组合就是50个2）。
• 边界处理：如果数组全是零，只有目标值为零时存在解（返回[0]），否则永远无解，但按题目要求需逐次加1的话，这里可直接返回[0]（因为零的和永远是零，加多少都无法得到正目标值）。

伪代码示例 #

def find_min_combination(items, quota):
    # 预处理
    unique_items = sorted(set(items))
    non_zero = [x for x in unique_items if x > 0]
    has_zero = 0 in unique_items

    if not non_zero:
        return [0] if has_zero else []  # 全零情况

    min_pos = non_zero[0]
    target = quota

    while True:
        # 检查单元素
        if target in unique_items:
            return [target]
        
        # 检查双元素
        seen = set()
        for num in non_zero:
            complement = target - num
            if complement in seen:
                return sorted([num, complement])
            seen.add(num)
        
        # 检查k≥3元素（动态规划）
        max_sum = target
        dp = [float('inf')] * (max_sum + 1)
        dp[0] = 0

        for num in non_zero:
            for s in range(num, max_sum + 1):
                if dp[s - num] + 1 < dp[s]:
                    dp[s] = dp[s - num] + 1
        
        if dp[target] != float('inf'):
            # 回溯找组合
            combo = []
            remaining = target
            for num in reversed(non_zero):
                while remaining >= num and dp[remaining - num] + 1 == dp[remaining]:
                    combo.append(num)
                    remaining -= num
                    if remaining == 0:
                        break
                if remaining == 0:
                    break
            return sorted(combo)
        
        # 无解决方案，目标值加1
        target += 1

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