面试题：如何生成元组所有不重复组合的和？

问题描述 #

我在面试中遇到了一道决策分析类的编程题：给定一个可能包含重复元素的元组，要求生成其所有不重复的组合和——也就是说，即使不同的组合计算出相同的数值，也只需要保留一次。举个具体的例子：

输入元组：(2, 2, 3)
所有可能的组合及对应和：

• 空组合：0
• 单个元素：2、2、3 → 去重后和为2、3
• 两个元素：2+2=4，2+3=5，2+3=5 → 去重后和为4、5
• 三个元素：2+2+3=7
  最终输出（顺序可灵活调整）：[0, 2, 3, 4, 5, 7]

核心思路 #

这道题的关键是避免重复计算相同的和，而重复的根源在于元组中存在重复元素，直接生成所有组合再求和会产生大量冗余。我们可以通过以下两步优化：

1. 预处理排序：先对元组排序，让相同元素相邻，方便后续跳过重复项。
2. 回溯+去重控制：用回溯法遍历所有可能的组合，遇到重复元素时，只处理一次该元素的选择逻辑，避免生成重复组合；同时用集合存储和，利用集合的自动去重特性确保结果唯一。

代码实现（Python） #

回溯法（直观易理解）

def unique_combination_sums(input_tuple):
    nums = sorted(input_tuple)
    unique_sums = set()
    
    def backtrack(current_index, current_total):
        # 先把当前的和加入集合（包括空组合的0）
        unique_sums.add(current_total)
        for i in range(current_index, len(nums)):
            # 跳过重复元素：如果当前元素和前一个相同，且不是当前分支的第一个元素，直接跳过
            if i > current_index and nums[i] == nums[i-1]:
                continue
            # 选择当前元素，递归处理下一个位置
            backtrack(i + 1, current_total + nums[i])
    
    backtrack(0, 0)
    # 集合转列表，顺序可按需调整
    return list(unique_sums)

# 测试示例
test_input = (2, 2, 3)
print(unique_combination_sums(test_input))  # 输出类似 [0, 2, 3, 4, 5, 7]

代码解释

• 排序后，相同元素会挨在一起，当我们在遍历到重复元素时，i > current_index 确保我们不会跳过第一个出现的元素，只跳过后续重复的，避免生成完全相同的组合。
• 集合unique_sums自动帮我们去重，不管多少种组合得到同一个和，最终只会保留一次。
• 回溯函数的初始调用backtrack(0, 0)对应空组合的和0，然后逐步添加元素生成所有可能的组合和。

迭代法（空间优化可选） #

如果不想用递归，也可以用迭代的方式逐步构建和的集合：

def unique_combination_sums_iterative(input_tuple):
    nums = sorted(input_tuple)
    sums = {0}
    prev_num = None
    for num in nums:
        # 处理重复元素：只和上一次新增的和相加，避免重复计算
        if num == prev_num:
            temp = set()
            for s in new_sums:
                temp.add(s + num)
            sums.update(temp)
            new_sums = temp
        else:
            new_sums = set()
            for s in sums:
                new_sum = s + num
                new_sums.add(new_sum)
            sums.update(new_sums)
        prev_num = num
    return list(sums)

这种方法通过记录上一次新增的和集合，避免重复元素重复计算所有已有和，效率更高一些。

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