如何编写函数从整数列表中提取所有元素和等于指定值的子集

核心实现思路 #

使用排序+回溯剪枝算法解决无重复组合求和问题：

• 先对输入整数列表排序，可提前终止无效递归，同时避免生成顺序不同的重复组合
• 回溯过程中仅遍历当前索引之后的元素，保证所有子集为升序排列，符合卡牌组合不考虑顺序的需求
• 已默认过滤长度为1的子集，匹配你已完成单张等值逻辑的现状

C# 代码实现 #

using System.Collections.Generic;
using System.Linq;

public class SubsetSumHelper
{
    /// <summary>
    /// 从输入列表中提取所有元素和等于目标值的子集（默认返回长度>=2的子集）
    /// </summary>
    /// <param name="sourceList">输入整数列表</param>
    /// <param name="targetSum">目标和</param>
    /// <returns>所有符合条件的子集</returns>
    public List<List<int>> GetTargetSumSubsets(List<int> sourceList, int targetSum)
    {
        List<List<int>> result = new List<List<int>>();
        // 先排序用于剪枝和避免重复组合
        List<int> sortedList = sourceList.OrderBy(x => x).ToList();
        Backtrack(sortedList, targetSum, 0, new List<int>(), 0, result);
        return result;
    }

    private void Backtrack(List<int> sortedList, int targetSum, int startIndex, List<int> currentPath, int currentSum, List<List<int>> result)
    {
        // 匹配到目标和
        if (currentSum == targetSum)
        {
            // 仅保留长度>=2的子集，如需包含单张可删除此判断
            if (currentPath.Count >= 2)
            {
                result.Add(new List<int>(currentPath));
            }
            return;
        }

        for (int i = startIndex; i < sortedList.Count; i++)
        {
            // 剪枝：当前元素已超过剩余需要的和，后续元素更大，直接终止循环
            if (currentSum + sortedList[i] > targetSum)
            {
                break;
            }

            // 加入当前元素
            currentPath.Add(sortedList[i]);
            // 递归遍历后续元素，避免生成顺序不同的重复组合
            Backtrack(sortedList, targetSum, i + 1, currentPath, currentSum + sortedList[i], result);
            // 回溯，移除当前元素尝试其他组合
            currentPath.RemoveAt(currentPath.Count - 1);
        }
    }
}

测试验证 #

调用示例：

List<int> list = new List<int>() { 1, 2, 3, 4, 5, 9 };
SubsetSumHelper helper = new SubsetSumHelper();
var subsets = helper.GetTargetSumSubsets(list, 10);

返回结果为：

• [1,2,3,4]
• [1,4,5]
• [2,3,5]
• [1,9]
  完全匹配预期输出。

扩展说明 #

• 代码未加入卡牌去重、子集大小比对逻辑，你可根据业务需求自行在返回结果中扩展处理
• 若后续需要支持包含单张卡牌的匹配结果，仅需删除Backtrack方法中currentPath.Count >= 2的判断即可

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