Get array of elements from list that sum to value

Question

Below is a simplified version of my question, the background summary underneath provides a greater context.

Problem:

Create a function that lists all elements from a list that sum to a given value in an array.

Given:

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

If the value provided was 10, then the function should return an array with lists 1, 2, 3, 4, and 1, 4, 5, and 2, 3, 5, and 1, 9.

---

Background:

I'm trying to digitize an old card game called Pastra (or Bastra) and the objective is to collect cards from the board. You can only collect cards that match the number value of a card or any numbered cards that sum to the played card's number. Ace's are 1s.

I already have the code for collecting the card that has an equal value.

What I need is to create an array of values from the original list with the elements that sum to the given value.

I'll need to know which list is larger as well as to know which list contains which cards so that the same card is not collected more than once. (Note: This is out of scope for this question. I want to discover that myself, however it's here to provide context as to why I need the information this way).

Example:

Same as above, if the board has an Ace, 2, 3, 4, 5, and 9, if I were to play a 10, I could collect Ace, 2, 3, 4, or Ace, 4, 5, or 2, 3, 5, or Ace, 9.

---

Thank you for your help, it's greatly appreciated.

Answer 1

Here is a recursive solution that finds all the combinations of positive numbers. It won't remove duplicate combinations if the set of numbers includes duplicate numbers.

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);
        }
    }
}

Answer 2

You first need to create combinations, then filter the list based on the sum

Given

This is basically a generic method that uses a bit mask to figure out what combination have been visited, i.e.. A 30 element array will occupy a number with 30 bits, it increments the number to make combinations of those bits... for every bit pattern it will return a combination of the original array

_{Note : This can be used with long or BigInteger if needed}

public static IEnumerable<T[]> GetCombinations<T>(T[] source)
{
   for (var i = 0; i < (1 << source.Length); i++)
      yield return source
         .Where((t, j) => (i & (1 << j)) != 0)
         .ToArray();
}

Filter

Not much to say here, filter the combinations based on Sum

public static IEnumerable<int[]> GetItems(IEnumerable<int> source, int target) 
   => GetCombinations(source.ToArray())
      .Where(items => items.Sum() == target);

Usage

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

foreach (var found in GetItems(list,10))
   Console.WriteLine(string.Join(", ", found));

Output

1, 2, 3, 4
2, 3, 5
1, 4, 5
1, 9