Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
487 views
in Technique[技术] by (71.8m points)

c# - Efficient algorithm to find a combination, which summation is equal to a known number, in a set of number

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);
See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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,

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

1.4m articles

1.4m replys

5 comments

57.0k users

...