如何找出总和为100的数字的所有排列

Question

我正在尝试找到一种有效的方法来创建一个方法，该方法采用包含多个连续整数列表的字典（每个列表必须从0或更高开始，到100或更低结束，但是确切的数字可能有所不同）并返回包含所有排列之和的所有数字之和的字典列表。

例如，对于4个类别：10 + 20 + 10 + 60 = 100

结果列表中的每个字典应为每个键存储一个整数值。

这是我想出的一些代码来说明我的问题：

using System;
using System.Collections.Generic;
using System.Linq;

namespace recursiveTest
{
    class Program
    {
        static void Main(string[] args)
        {
            Dictionary<string, List<int>> data = new Dictionary<string, List<int>>();
            data.Add("A", Enumerable.Range(0, 100).ToList());
            data.Add("B", Enumerable.Range(0, 100).ToList());
            data.Add("C", Enumerable.Range(0, 100).ToList());
            data.Add("D", Enumerable.Range(0, 100).ToList());
            // I would like to add a few entries more...

            List<Dictionary<string, int>> permutations = new List<Dictionary<string, int>>();

            foreach (var a in data["A"])
            {
                foreach (var b in data["B"])
                {
                    foreach (var c in data["C"])
                    {
                        foreach (var d in data["D"])
                        {
                            if (a + b + c + d == 100)
                            {
                                var current = new Dictionary<string, int>()
                                {
                                    ["A"] = a,
                                    ["B"] = b,
                                    ["C"] = c,
                                    ["D"] = d,
                                };
                                permutations.Add(current);
                            }
                        }
                    }
                }
            }

            Console.WriteLine($"Found (foreach): {permutations.Count()}");
            Console.ReadKey();
        }
    }
}
使用LINQ的替代方法：

            List<Dictionary<string, int>> permutations2 = (from a in data["A"]
                                                           from b in data["B"]
                                                           from c in data["C"]
                                                           from d in data["D"]
                                                           where a + b + c + d == 100
                                                           let current = new Dictionary<string, int>()
                                                           {
                                                               ["A"] = a,
                                                               ["B"] = b,
                                                               ["C"] = c,
                                                               ["D"] = d,
                                                           }
                                                           select current).ToList();

            Console.WriteLine($"Found (LINQ): {permutations2.Count()}");
            Console.ReadKey();
在类别（字典键）和数字开始增长之前，这不是一个非常复杂的任务...由于字典键（类别）的数量可能有所不同，因此这似乎是递归的潜在候选人，但是我无法使其工作。这两个版本有一些明显的缺点：

1. 项目和/或类别的数量一旦增加，性能就会突然下降。
2. 箭头形代码似乎是灾难的根源。
3. [它试图遍历所有可能的组合，而实际上只有少数有用（那些总计为100）。

获得简短结果，可读性强且性能良好的最佳方法是什么？

是否有一种方法可以找出不必要的循环，同时找出这100个和值？

---

编辑：

为了澄清起见，我的想法是能够定义一个具有如下签名的方法：

private static List<Dictionary<string, int>> GetValidPermutations(Dictionary<string, List<int>> data)
然后这样称呼它：

List<Dictionary<string, int>> permutations = GetValidPermutations(data);

[我正在尝试找到一种有效的方法来创建一个方法，该方法采用包含多个连续整数列表的字典（每个列表必须从0或更高开始，以100或更低开始，...

Answer 1

为了提高性能，关键是减少不必要的迭代次数：

Answer 2

如果我很了解您的问题，我建议采用此解决方案