The algorithm for finding a group of numbers in a list that is equal to the target

Question

So here is what I am trying to do. I have a list of integers:

List<int> myList = new List<int>() {5,7,12,8,7};

And I also have a goal:

int target = 20;

What I'm trying to do is find a way to create a new integer list that when merged will be equal to my goal. Therefore, if my goal is 20, I need a list like this:

{ 12, 8 }

If my goal is 26, I will have the following:

{ 7, 12, 7 }

Each number can be used only once (7 is used twice because it is listed twice). If there is no solution, it should return an empty list. Does anyone know how I can do something like this?

Answer 1

. . , :

http://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-C-G

:

List<int> myList = new List<int>() { 5, 7, 12, 8, 7 };
var allMatchingCombos = new List<IList<int>>();
for (int lowerIndex = 1; lowerIndex < myList.Count; lowerIndex++)
{
    IEnumerable<IList<int>> matchingCombos = new Combinations<int>(myList, lowerIndex, GenerateOption.WithoutRepetition)
        .Where(c => c.Sum() == 20);
    allMatchingCombos.AddRange(matchingCombos);
}

foreach(var matchingCombo in allMatchingCombos)
    Console.WriteLine(string.Join(",", matchingCombo));

:

12,8
5,7,8
5,8,7

Answer 2

. , , , . , 20 12+8 , 5+7+8.

List<int> findSum(List<int> numbers, int target, int index = 0)
{
    // loop through all numbers starting from the index
    for (var i = index; i < numbers.Count; i++)
    {
        int remainder = target - numbers[i];
        // if the current number is too big for the target, skip
        if (remainder < 0)
            continue;
        // if the current number is a solution, return a list with it
        else if (remainder == 0)
            return new List<int>() { numbers[i] };
        else
        {
            // otherwise try to find a sum for the remainder later in the list
            var s = findSum(numbers, remainder, i + 1);

            // if no number was returned, we could’t find a solution, so skip
            if (s.Count == 0)
                continue;

            // otherwise we found a solution, so add our current number to it
            // and return the result
            s.Insert(0, numbers[i]);
            return s;
        }
    }

    // if we end up here, we checked all the numbers in the list and
    // found no solution
    return new List<int>();
}

void Main()
{
    List<int> myList = new List<int>() { 5, 7, 12, 8, 7 };

    Console.WriteLine(findSum(myList, 12)); // 5, 7
    Console.WriteLine(findSum(myList, 20)); // 5, 7, 8
    Console.WriteLine(findSum(myList, 31)); // 5, 7, 12, 7
}

Answer 3

: https://github.com/Mr-Zoidberg/Find-Possible-Combinations

1.

static void Main(string[] args)
    {
        const int target = 20;
        var numbers = new List<int> { 1, 2, 5, 8, 12, 14, 9 };

        Console.WriteLine($"Number of Combinations: {SumCounter(numbers, target)}");
        Console.ReadKey();
    }


    private static int SumCounter(IReadOnlyList<int> numbers, int target)
    {
        var result = 0;
        RecursiveCounter(numbers, target, new List<int>(), ref result);
        return result;
    }

    private static void RecursiveCounter(IReadOnlyList<int> numbers, int target, List<int> partial, ref int result)
    {
        var sum = partial.Sum();
        if (sum == target)
        {
            result++;
            Console.WriteLine(string.Join(" + ", partial.ToArray()) + " = " + target);
        }

        if (sum >= target) return;

        for (var i = 0; i < numbers.Count; i++)
        {
            var remaining = new List<int>();
            for (var j = i + 1; j < numbers.Count; j++) remaining.Add(numbers[j]);
            var partRec = new List<int>(partial) { numbers[i] };
            RecursiveCounter(remaining, target, partRec, ref result);
        }
    }

2. Linq

static void Main(string[] args)
    {
        const int target = 20;
        var numbers = new int[] { 1, 2, 5, 8, 12, 14, 9 };

        var matches = numbers.GetSubsets().Where(s => s.Sum() == target).ToArray();

        foreach (var match in matches) Console.WriteLine(match.Select(m => m.ToString()).Aggregate((a, n) => $"{a} + {n}") + $" = {target}");

        Console.WriteLine($"Number of Combinations: {matches.Length}");
        Console.ReadKey();
    }
}

public static class Extension
{
    public static IEnumerable<IEnumerable<T>> GetSubsets<T>(this IEnumerable<T> collection)
    {
        if (!collection.Any()) return Enumerable.Repeat(Enumerable.Empty<T>(), 1);
        var element = collection.Take(1);
        var ignoreFirstSubsets = GetSubsets(collection.Skip(1));
        var subsets = ignoreFirstSubsets.Select(set => element.Concat(set));
        return subsets.Concat(ignoreFirstSubsets);
    }

3. ...

static void Main(string[] args)
    {
        const int target = 20;
        var numbers = new [] { 1, 2, 5, 8, 12, 14, 9 };
        var result = GetSubsets(numbers, target, "");

        foreach (var subset in result) Console.WriteLine($"{subset} = {target}");
        Console.WriteLine($"Number of Combinations: {result.Count()}");
        Console.ReadLine();
    }

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

4. . .

static void Main(string[] args)
    {
        const int target = 20;
        var numbers = new [] { 1, 2, 5, 8, 12, 14, 9 };

        var subsets = GetSubsets(numbers, target);

        foreach (var s in subsets) Console.WriteLine($"{s} = {target}");
        Console.WriteLine($"Number of Combinations: {subsets.Count()}");
        Console.ReadKey();
    }


    private static IEnumerable<string> GetSubsets(int[] array, int target)
    {      
        Array.Sort((Array)array);
        List<string> result = new List<string>();

        for (int i = array.Length-1; i >= 0; i--)
        {
            var eq = $"{array[i]}";
            var sum = array[i];
            var toAdd = 0;

            while (sum != target)
            {
                var mid = Array.BinarySearch(array, 0, sum <= target / 2 && sum != array[i] ? array.Length - 1 : i, target - sum);
                mid = mid < 0 ? ~mid - 1 : mid;
                if (mid == i  || mid < 0 || toAdd == array[mid] ) break;

                toAdd = array[mid];
                sum += array[mid];
                eq += $" + {array[mid]}";
                if (sum == target) result.Add(eq);
            }
        }
        return result;
    }