数组中和为目标值的元素集合求解：代码异常求助

你的代码核心问题是用了贪心算法来解决子集和问题，但贪心策略并不适用于这类场景——它只能找到“尽可能接近目标的最大和”，无法保证找到刚好等于目标值的元素组合。

具体问题分析 #

在输入Target=10、数组[2,3,3,4]时：

1. 代码先将数组排序为[2,3,3,4]
2. 贪心遍历累加：2+3+3=8，再加4会超过10，因此停止，此时selected为[2,3,3]
3. 代码判断总和8<10，直接清空selected，最终输出“No elements available”
4. 但实际上存在合法组合：3+3+4=10，贪心策略因优先选择小元素，错过了这个正确组合

修复方案：用回溯法解决子集和问题 #

子集和问题属于NP问题，针对小规模输入，回溯法是直观有效的解决方案。以下是修复后的代码：

arr = []
target = int(input("Enter the target: "))
n = int(input("Enter the number of elements: "))

for i in range(n):
    arr.append(int(input()))

result = []

def backtrack(start, current_sum, path):
    if current_sum == target:
        result.append(path.copy())
        return
    if current_sum > target:
        return
    for i in range(start, n):
        # 跳过重复元素避免生成重复组合（可选，根据需求调整）
        if i > start and arr[i] == arr[i-1]:
            continue
        path.append(arr[i])
        backtrack(i+1, current_sum + arr[i], path)
        path.pop()

backtrack(0, 0, [])

if not result:
    print("No elements available")
else:
    # 输出第一个找到的组合，若需要全部组合可改为print(*result, sep="\n")
    print(*result[0])

代码说明 #

• 回溯法通过递归尝试所有可能的元素组合，当当前和等于目标时记录路径
• 加入重复元素跳过逻辑，避免生成如[3(第一个),3(第二个),4]和[3(第二个),3(第一个),4]这类重复组合（不需要去重可删除该判断）
• 找到所有符合条件的组合后，可根据需求选择输出第一个、全部或其他筛选结果

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