This post includes code (C#) to find combinations that equal a given sum. The ordering of numbers is not important for this kind of problem and every combination of numbers does not have to be a fixed count.

Say that you have a collection of numbers [2, 4, 2] and want to find every combination that have a sum of 4. The number of possible combinations when there is 3 numbers is 7 ((2^Count)-1) and it is 2 combinations that give the sum of 4 (2+2, 4).

### Code

This is a console application that takes input from a command prompt and outputs all combinations that equal a target sum. If you just want to find the first combination that equal a given sum, break out from the loop when the sum has been found.

```
using System;
using System.Linq;
using System.Collections.Generic;
namespace Annytab
{
public class SumCombinations
{
public static Int32 Main(string[] args)
{
// Get input
int target_sum = Convert.ToInt32(Console.ReadLine());
string[] input = Console.ReadLine().Split(' ');
// Create lists
List<Int32> numbers = new List<Int32>();
List<Int32[]> output_indexes = new List<Int32[]>();
List<Int32[]> output_numbers = new List<Int32[]>();
// Add numbers
for (int i = 0; i < input.Length; i++)
{
numbers.Add(Convert.ToInt32(input[i]));
}
// Calculate the number of combinations
Int32 combinations = (Int32)(Math.Pow(2, numbers.Count) - 1);
// Loop all combinations
for (int i = 0; i < combinations; i++)
{
// Create subset lists
List<Int32> subset = new List<Int32>();
List<Int32> subindexes = new List<Int32>();
// Loop all numbers
for (int j = 0; j < numbers.Count; j++)
{
if (((i & (1 << j)) >> j) == 1)
{
// Add the number and the index
subset.Add(numbers[j]);
subindexes.Add(j);
}
}
// Check if the target sum has been reached
if (subset.Sum() == target_sum)
{
// Add a combination
output_indexes.Add(subindexes.ToArray());
output_numbers.Add(subset.ToArray());
//break;
}
}
// Write output
Console.WriteLine("\nOutput");
Console.WriteLine("---------------------------------------------------");
// Loop output
for (int i = 0; i < output_indexes.Count; i++)
{
Console.WriteLine(string.Join(" ", output_indexes[i]) + " (" + string.Join(" + ", output_numbers[i]) + " = " + target_sum.ToString() + ")");
}
Console.WriteLine("---------------------------------------------------");
// Pause the program
Console.ReadKey();
// Return success
return 0;
} // End of the Main method
} // End of the class
} // End of the namespace
```

### Example: Output from program

```
12
4 5 6 7 3 2 2 2 8 6
Output
---------------------------------------------------
1 3 (5 + 7 = 12)
0 1 4 (4 + 5 + 3 = 12)
0 2 5 (4 + 6 + 2 = 12)
3 4 5 (7 + 3 + 2 = 12)
0 2 6 (4 + 6 + 2 = 12)
3 4 6 (7 + 3 + 2 = 12)
1 4 5 6 (5 + 3 + 2 + 2 = 12)
0 2 7 (4 + 6 + 2 = 12)
3 4 7 (7 + 3 + 2 = 12)
1 4 5 7 (5 + 3 + 2 + 2 = 12)
1 4 6 7 (5 + 3 + 2 + 2 = 12)
2 5 6 7 (6 + 2 + 2 + 2 = 12)
0 8 (4 + 8 = 12)
5 6 8 (2 + 2 + 8 = 12)
5 7 8 (2 + 2 + 8 = 12)
6 7 8 (2 + 2 + 8 = 12)
2 9 (6 + 6 = 12)
0 5 9 (4 + 2 + 6 = 12)
0 6 9 (4 + 2 + 6 = 12)
0 7 9 (4 + 2 + 6 = 12)
5 6 7 9 (2 + 2 + 2 + 6 = 12)
---------------------------------------------------
25
12 14 6 8 7 5 13 20 4
Output
---------------------------------------------------
0 2 4 (12 + 6 + 7 = 25)
1 2 5 (14 + 6 + 5 = 25)
0 3 5 (12 + 8 + 5 = 25)
0 6 (12 + 13 = 25)
4 5 6 (7 + 5 + 13 = 25)
5 7 (5 + 20 = 25)
1 4 8 (14 + 7 + 4 = 25)
2 3 4 8 (6 + 8 + 7 + 4 = 25)
3 6 8 (8 + 13 + 4 = 25)
---------------------------------------------------
```