Get Numbers Combination to a Target Sum - C#

I have a target number and a list of numbers. I need to find a combination from the list which sum of them is the target number.

Example:

list = [1,2,3,10]
target = 12
result = [2,10]

Here is a class which will do this:

public class Solver {

    private List<List<decimal>> mResults;

    public List<List<decimal>> Solve(decimal goal, decimal[] elements) {

        mResults = new List<List<decimal>>();
        RecursiveSolve(goal, 0.0m, 
            new List<decimal>(), new List<decimal>(elements), 0);
        return mResults; 
    }

    private void RecursiveSolve(decimal goal, decimal currentSum, 
        List<decimal> included, List<decimal> notIncluded, int startIndex) {
        if (mResults.Count > 0) return;
        for (int index = startIndex; index < notIncluded.Count; index++) {

            decimal nextValue = notIncluded[index];
            if (currentSum + nextValue == goal) {
                List<decimal> newResult = new List<decimal>(included);
                newResult.Add(nextValue);
                if (mResults.Count == 0)
                   mResults.Add(newResult);
                else
                   break;
            }
            else if (currentSum + nextValue < goal) {
                List<decimal> nextIncluded = new List<decimal>(included);
                nextIncluded.Add(nextValue);
                List<decimal> nextNotIncluded = new List<decimal>(notIncluded);
                nextNotIncluded.Remove(nextValue);
                RecursiveSolve(goal, currentSum + nextValue,
                    nextIncluded, nextNotIncluded, startIndex++);
            }
        }
    }
}

It will find the first combination of numbers which sum to target number. well, but when the list is bigger it takes so many time to find the combination as long as it is easy to find. like this:

Target number is= 100;

list is:

90
0.56
10
and so many other numbers

it will sum 90 with 0.56 so it will be 90.56 and then it will search to complete it into 100, but as long as 90 + 10 (index 0 and 2) will be 100.

How to edit this method to do its job faster and smarter?

1 answer

  • answered 2021-10-25 02:36 AniOptics

    If I had enough reputation to comment, then I would. Your question has likely been answered already (what youre looking for are called permutations). As far as performance goes, you want to limit how many iterations you perform. Here is a link to another stackoverflow question that should answer yours:

    How to find out all permutations of numbers that sum to 100

How many English words
do you know?
Test your English vocabulary size, and measure
how many words do you know
Online Test
Powered by Examplum