algorithm to find the correct set of numbers

Question

i will take either python of c# solution

i have about 200 numbers:

 19.16 
 98.48 
 20.65 
 122.08 
 26.16 
 125.83 
 473.33 
 125.92 
 3,981.21 
 16.81 
 100.00 
 43.58 
 54.19 
 19.83 
 3,850.97 
 20.83 
 20.83 
 86.81 
 37.71 
 36.33 
 6,619.42 
 264.53 
...
...

i know that in this set of numbers, there is a combination of numbers that will add up to a certain number let's say it is 2341.42

how do i find out which combination of numbers will add up to that?

i am helping someone in accounting track down the correct numbers

Answer 1

Try the following approach if finding a combination of any two (2) numbers:

float targetSum = 3;

float[] numbers = new float[]{1, 2, 3, 4, 5, 6};

Sort(numbers); // Sort numbers in ascending order.

int startIndex = 0;
int endIndex = numbers.Length - 1;

while (startIndex != endIndex)
{
   float firstNumber = numbers[startIndex];
   float secondNumber = numbers[endIndex];

   float sum = firstNumber + secondNumber;

   if (sum == targetSum)
   {
      // Found a combination.
      break;
   }
   else if (sum < targetSum)
   {
      startIndex++;
   }
   else
   {
      endIndex--;
   }
}

Remember that when use floating-point or decimal numbers, rounding could be an issue.

Answer 2

This should be implemented as a recursive algorithm. Basically, for any given number, determine if there is a subset of the remaining numbers for which the sum is your desired value.

Iterate across the list of numbers; for each entry, subtract that from your total, and determine if there is a subset of the remaining list which sums up to the new total. If not, try with your original total and the next number in the list (and a smaller sublist, of course).

As to implementation: You want to define a method which takes a target number, and a list, and which returns a list of numbers which sum up to that target number. That algorithm should iterate through the list; if an element of the list subtracted from the target number is zero, return that element in a list; otherwise, recurse on the method with the remainder of the list, and the new target number. If any recursion returns a non-null result, return that; otherwise, return null.

ArrayList<decimal> FindSumSubset(decimal sum, ArrayList<decimal> list)
{
   for (int i = 0; i < list.Length; i++)
   {
      decimal value = list[i];
      if (sum - value == 0.0m)
      {
          return new ArrayList<decimal>().Add(value);
      }
      else
      {
          var subset = FindSumSubset(sum - value, list.GetRange(i + 1, list.Length -i);
          if (subset != null)
          {
              return subset.Add(value);
          }
      }
   }
   return null;
}

Note, however, that the order of this is pretty ugly, and for significantly larger sets of numbers, this becomes intractable relatively quickly. This should be doable in less than geologic time for 200 decimals, though.

Answer 3

[Begin Edit]:

I misread the original question. I thought that it said that there is some combination of 4 numbers in the list of 200+ numbers that add up to some other number. That is not what was asked, so my answer does not really help much.

[End Edit]

This is pretty clunky, but it should work if all you need is to find the 4 numbers that add up to a certain value (it could find more than 4 tuples):

Just get your 200 numbers into an array (or list or some IEnumerable structure) and then you can use the code that I posted. If you have the numbers on paper, you will have to enter them into the array manually as below. If you have them in softcopy, you can cut and paste them and then add the numbers[x] = xxx code around them. Or, you could cut and paste them into a file and then read the file from disk into an array.

  double [] numbers = new numbers[200];
  numbers[0] = 123;
  numbers[1] = 456; 

  //
  // and so on.
  //

  var n0 = numbers;
  var n1 = numbers.Skip(1);
  var n2 = numbers.Skip(2);
  var n3 = numbers.Skip(3);

  var x = from a in n0
          from b in n1
          from c in n2
          from d in n3
          where a + b + c + d == 2341.42
          select new { a1 = a, b1 = b, c1 = c, d1 = d };

  foreach (var aa in x)
  {
    Console.WriteLine("{0}, {1}, {2}, {3}", aa.a1, aa.b1, aa.c1, aa.d1 );
  }

Answer 4

You can use backtracking to generate all the possible solutions. This way you can quickly write your solution.

EDIT:

You just implement the algoritm in C#:

public void backtrack (double sum, String solution, ArrayList numbers, int depth, double targetValue, int j)
{
    for (int i = j; i < numbers.Count; i++)
        {
            double potentialSolution = Convert.ToDouble(arrayList[i] + "");
            if (sum + potentialSolution > targetValue)
                continue;
            else if (sum + potentialSolution == targetValue)
            {
                if (depth == 0)
                {
                    solution = potentialSolution + "";
                    /*Store solution*/
                }
                else
                {
                    solution += "," + potentialSolution;
                    /*Store solution*/
                }
            }
            else
            {
                if (depth == 0)
                {
                    solution = potentialSolution + "";
                }
                else
                {
                    solution += "," + potentialSolution;
                }
                backtrack (sum + potentialSolution, solution, numbers, depth + 1, targetValue, i + 1);
            }
        }
}

You will call this function this way:

backtrack (0, "", numbers, 0, 2341.42, 0);

The source code was implemented on the fly to answer your question and was not tested, but esencially you can understand what I mean from this code.

Answer 5

Here's a recursive function in Python that will find ALL solutions of any size with only two arguments (that you need to specify).

def find_all_sum_subsets(target_sum, numbers, offset=0):
    solutions = []
    for i in xrange(offset, len(numbers)):
        value = numbers[i]
        if target_sum == value:
            solutions.append([value])
        elif target_sum > value:
            sub_solutions = find_all_sum_subsets(target_sum - value, numbers, i + 1)
            for sub_solution in sub_solutions:
                solutions.append(sub_solution + [value])
    return solutions

Here it is working:

>>> find_all_sum_subsets(10, [1,2,3,4,5,6,7,8,9,10,11,12])
[[4, 3, 2, 1], [7, 2, 1], [6, 3, 1], [5, 4, 1], [9, 1], [5, 3, 2], [8, 2], [7, 3], [6, 4], [10]]
>>>