Pick a varying number of item combinations from a List

Viewed 106

Assume I have a list of integers of any length, for an example I have the list of 1,3,5 and 7.

I would like an algorithm to pick a combination of X elements from the list.

For example, X = 1 would return:

1

3

5

7

x = 2 would return:

1 + 1

1 + 3

1 + 5

1 + 7

3 + 3

3 + 5

3 + 7

5 + 5

5 + 7

7 + 7

var listOfInts = new List<int> { 1, 3, 5, 7 };
var combinedInts = new List<int>();

// x = 1 solution
// This is only picking one item from the list. 
for (int i = 0; i < listOfInts.Count(); i++)
{
    combinedInts.Add(listOfInts[i]);
}

// x = 2 solution
// This is how to pick two. I wrap it around another for loop.
for (int i = 0; i < listOfInts.Count(); i++)
{
    for (int j = i; j < listOfInts.Count(); j++)
    {
        combinedInts.Add(listOfInts[i] + listOfInts[j]);
    }
}

// x = 3 solution
// If I go up another level I have to wrap it around another for loop. This solution won't scale.
for (int i = 0; i < listOfInts.Count(); i++)
{
    for (int j = i; j < listOfInts.Count(); j++)
    {
        for (int k = j; k < listOfInts.Count(); k++)
        {
            combinedInts.Add(listOfInts[i] + listOfInts[j] + listOfInts[k]);
        }
    }
}

This solution doesn't scale as I have to continually wrap around another for loop for each number of element I'm picking. For example X = 7 would need 7-nested for loops. Is there a better way to write this method that doesn't involve nesting for loops?

3 Answers
Related