An effective algorithm for finding a combination whose sum is a known number in a set of numbers

Question

Say there are many numbers

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

I want to find several combinations in a set of numbers, so that summing it is equal to a known number, for example, 18. We can find out that 5, 6, 7 matches (5 + 6 + 7 = 18).

The numbers in the combination cannot be repeated, and the number in the set may not match.

I wrote a C # program for this. The program is random to pick up a number to form a combination, and check if the summation of the combination matches the known number. However, the combination of the found program can be repeated, and this makes progress ineffective.

I am wondering if there is any efficient algorithm for finding such a combination.

Here is part of my code.

int Sum = 0; int c; List<int> Pick = new List<int>(); List<int> Target = new List<int>() {some numbers} Target.Sort(); while (!Target.Contains(Sum)) { if (Sum > Target[Target.Count - 1]) { Pick.Clear(); Sum = 0; } while (true) { if (Pick.IndexOf(c = Math0.rand(0, Set.Count - 1)) == -1) { Pick.Add(c); } //Summation Pick Sum = 0; for (int i = 0; i < Pick.Count; i++) Sum += Set[Pick[i]]; if (Sum >= Target[Target.Count - 1]) break; } } Result.Add(Pick); 

Answer 1

You can use recursion. For any given number in the set, find combinations of smaller numbers that are added before the number:

 public static IEnumerable<string> GetCombinations(int[] set, int sum, string values) { for (int i = 0; i < set.Length; i++) { int left = sum - set[i]; string vals = set[i] + "," + values; if (left == 0) { yield return vals; } else { int[] possible = set.Take(i).Where(n => n <= sum).ToArray(); if (possible.Length > 0) { foreach (string s in GetCombinations(possible, left, vals)) { yield return s; } } } } } 

Using:

 int[] set = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; foreach (string s in GetCombinations(set, 18, "")) { Console.WriteLine(s); } 

Output:

 1,2,4,5,6, 3,4,5,6, 1,2,3,5,7, 2,4,5,7, 2,3,6,7, 1,4,6,7, 5,6,7, 1,2,3,4,8, 2,3,5,8, 1,4,5,8, 1,3,6,8, 4,6,8, 1,2,7,8, 3,7,8, 2,3,4,9, 1,3,5,9, 4,5,9, 1,2,6,9, 3,6,9, 2,7,9, 1,8,9, 1,3,4,10, 1,2,5,10, 3,5,10, 2,6,10, 1,7,10, 8,10, 

Answer 2

Possible alternative method. With a small kit like this, you can use brute force. Your set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} has 10 elements, and each element may or may not be present. This can be matched with a binary number between 0 (= 0b0000000000) and 1023 (= 0b1111111111). Number the numbers from 0 to 1023 inclusive and check the sum for the subset corresponding to the set bits of the binary representation of the number.

Maybe not the most useful for this particular question, but a good way to generate all possible subsets of a given set.