7

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

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

And I also got a target:

int target = 20;

What I'm trying to do is find a way to create a new list of integer that when added together equal my target. So if my target is 20, I need a list like this:

{ 12, 8 }

If my target is 26, then I'll have this:

{ 7, 12, 7 }

Each number can only be used one time (7 is used twice because its in the list twice). If there is no solution, it should return an empty list. Anyone have any idea how I can do something like this?

4

4 回答 4

4

这是一个统计问题。您想找到所有可能的组合以及匹配的总和。我可以推荐这个项目，它也值得一读：

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

然后它很简单有效：

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
于 2013-10-17T21:50:36.297 回答
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
}
于 2013-10-17T22:05:54.043 回答
2

您可以在这里找到下面给出的所有解决方案：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;
    }
于 2015-10-28T11:03:48.873 回答
0

我在 C# 中的这个实现将返回等于给定数字的所有组合（包括重复使用相同的数字）。

string r;
List<int> l = new List<int>();
void u(int w, int s, int K, int[] A) { 
    // If a unique combination is found 
    if (s == K) { 
        r += "(" + String.Join(" ", l) + ")";
        return; 
    } 
    // For all other combinations
    for (int i=w; i<A.Length; i++){
        // Check if the sum exceeds K 
        int x = A[i];
        if (s + x <= K){
            l.Add(x);
            u(i, s + x, K,A);
            l.Remove(x);
        }
    }
} 
string combinationSum(int[] a, int s) {
    r = "";
    u(0, 0, s, a.Distinct().OrderBy(x=>x).ToArray());
    return r.Any() ? r : "Empty";
}

对于 a: [2, 3, 5, 9] 和 s = 9

结果将是：“（2 2 2 3）（2 2 5）（3 3 3）（9）”

于 2020-04-04T17:16:41.310 回答