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

            // 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)
---------------------------------------------------