从该和到值的列表中获取元素数组

Question

下面是我问题的简化版本，下面的背景摘要提供了一个更好的背景。

问题：

创建一个函数，该函数列出数组中与给定值之和的列表中的所有元素。

Given:

List<int> list = new List<int>() { 1, 2, 3, 4, 5, 9 };

如果提供的值为10，则函数应该返回一个数组，其中包含列表1、2、3、4和1、4、5、2、3、5和1、9。

背景：

我正在尝试数字化一个名为Pastra (或Bastra)的旧纸牌游戏，目的是从董事会收集卡片。您只能收集与牌号值相匹配的卡，也只能收集与牌号相加的任何编号卡。王牌是1分。

我已经有了收集具有同等价值的卡片的代码。

我需要的是从原始列表中创建一个包含与给定值之和的元素的值数组。

我需要知道哪个列表更大，以及知道哪个列表包含哪些卡片，这样同一张卡片就不会被收集超过一次。(注:这超出了这个问题的范围。我想要自己发现，然而，它是为了提供上下文，为什么我需要这种方式的信息)。

示例：

和上面一样，如果董事会有一个Ace，2，3，4，5和9，如果我要玩10，我可以收集Ace，2，3，4，或者Ace，4，5，或者2，3，5，或者Ace，9。

谢谢你的帮助，非常感谢。

Answer 1

这里是一个递归的解决方案，它可以找到所有正数的组合。如果数字集包含重复数字，它不会删除重复的组合。

IEnumerable<IReadOnlyList<int>> FindCombosThatAddToValue(IReadOnlyList<int> numbers, int value)
{
    var indices = new BitArray(numbers.Count);
    var combos = new List<IReadOnlyList<int>>();
    FindCombos(0, 0);
    return combos;

    void FindCombos(int index, int total)
    {
        if (index >= numbers.Count)
            return;

        var n = numbers[index];
        var newTotal = total + n;

        if (newTotal == value)
        {
            // this is a matching combo so lets return it
            var combo = new List<int>();

            for (int i = 0; i < index; i++)
            {
                if (indices[i])
                {
                    combo.Add(numbers[i]);
                }
            }
            
            combo.Add(n);
            combos.Add(combo);
        }
        else
        {
            if (newTotal < value)
            {
                // try for more including this number/index
                indices.Set(index, true); // index included in total
                FindCombos(index + 1, newTotal);
            }

            // try for more not including this number/index
            indices.Set(index, false); // index not included in total
            FindCombos(index + 1, total);
        }
    }
}