# Find combinations that equal a given sum in C#

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[]>();

for (int i = 0; i < input.Length; 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
}
}

// Check if the target sum has been reached
if (subset.Sum() == target_sum)
{
// Add a combination
//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

// 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)
---------------------------------------------------``````
Tags: