Hitta kombinationer som ger en given summa i C#

Det här inlägget innehåller kod (C#) för att hitta alla kombinationer som motsvarar en given summa. Siffrornas ordning är inte viktig för denna typ av problem och varje kombination av siffror behöver inte vara ett fast antal.

Säg att du har en samling av nummer [2, 4, 2] och vill hitta varje kombination som summerar till 4. Antalet möjliga kombinationer när det finns 3 nummer är 7 ((2^Antal)-1) och det är 2 kombinationer som summerar till 4 (2+2, 4).

Kod

Det här är ett konsolprogram som får indata från en kommandotolk och matar ut alla kombinationer som motsvarar en målsumma. Om du bara vill hitta den första kombinationen som motsvarar en given summa, bryt ut från loopen när summan har hittats.

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

Exempel: Utmatning från programmet

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