11

Let's say there is a set of number

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

I want to find out several combinations in the set of number such that the summation of it equal to a known number, for example, 18. We can find out that 5, 6, 7 is matched (5+6+7=18).

Numbers in a combination cannot be repeated and the number in a set may not be consecutive.

I've wrote a C# program to do that. The program is random to pick up number to form a combination and check whether the summation of combination is equal to a known number. However, the combination the program found may be repeated and it makes the progress not effective.

I am wondering whether there is any efficient algorithm to find out such combination.

Here's 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);
Bill the Lizard
  • 398,270
  • 210
  • 566
  • 880
Ben
  • 5,069
  • 4
  • 18
  • 26
  • 3
    This is the Subset Sum problem: http://en.wikipedia.org/wiki/Subset_sum_problem – mbeckish May 24 '12 at 13:59
  • This was asked earlier this week. – user703016 May 24 '12 at 14:03
  • 1
    possible duplicate of [Algorithm to find which numbers from a list of size n sum to another number](http://stackoverflow.com/questions/83547/algorithm-to-find-which-numbers-from-a-list-of-size-n-sum-to-another-number) – mbeckish May 24 '12 at 14:05

2 Answers2

29

You can use recursion. For any given number in the set, find the combinations of smaller numbers that adds up to 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;
        }
      }
    }
  }
}

Usage:

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,
Guffa
  • 687,336
  • 108
  • 737
  • 1,005
1

A possible alternative method. With a small set like this, you could use brute force. Your set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} has 10 elements, and each element can be present or not present. That can be mapped to a binary number between 0 (= 0b0000000000) and 1023 (= 0b1111111111). Loop through 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.

rossum
  • 15,344
  • 1
  • 24
  • 38
  • can you explain 1023 please. How do you find 1023 the height number to check? – Krishna Karki Nov 23 '16 at 12:13
  • There are ten numbers in the problem: 1, 2, 3, ... 10. Each of those ten numbers can either be included in the result (1) or excluded from the result (0). Use 0000000000 to represent all numbers excluded and 1111111111 to represent all numbers included. Other possible results are between those two, like: 1001010011. Now represent all possible results as binary numbers. 0b0000000000 = 0 and 0b1111111111 = 1023. That is where the 1023 comes from: (2^10) - 1. For a problem with 12 numbers to check use (2^12) - 1 = 4095 – rossum Nov 23 '16 at 12:34