如何高效生成总和在指定范围内的所有组合（在所有深度）

假设您有一组值 (1,1,1,12,12,16）如何生成总和在预定义范围内的所有可能组合（不重复）[min,max]。例如，这里是（所有深度的）范围在13 and 17:

1 12

1 1 12

1 1 1 12

16

1 16

这假设具有相同值的每个项目是无法区分的，因此您不会得到以下三个结果1 12在最终输出中。蛮力是可能的，但在项目数量很大的情况下，所有深度的组合数量都是天文数字。在上面的示例中，所有深度都有 (3 + 1) * (2 + 1) * (1 + 1) = 24 种组合。因此，总组合是任何给定值的项目数 + 1 的乘积。当然，我们可以从逻辑上丢弃大量其部分总和大于最大值的组合（例如，集合16 12已经大于最大值17，因此跳过任何具有16 and 12在他们中）。

我最初认为我可以将输入数组转换为两个数组并像里程表一样递增它们。但我完全陷入了这种提前崩溃的递归算法。有什么建议么？

{
    int uniqueValues = 3;
    int[] maxCounts = new int[uniqueValues];
    int[] values = new int[uniqueValues];

    // easy code to bin the data, just hardcoding for example
    maxCounts[0] = 3;
    values[0] = 1;
    maxCounts[1] = 2;
    values[1] = 12;
    maxCounts[2] = 1;
    values[2] = 16;

    GenerateCombinationsHelper(new List<int[]>(), 13, 17, 0, 0, maxCounts, new int[3], values);
}

private void GenerateCombinationsHelper(List<int[]> results, int min, int max, int currentValue, int index, int[] maxValues, int[] currentCombo, int[] values)
{
    if (index >= maxValues.Length)
    {
        return;
    }

    while (currentCombo[index] < maxValues[index])
    {
        currentValue += values[index];

        if (currentValue> max)
        {                   
            return;
        }

        currentCombo[index]++;

        if (currentValue< min)
        {                    
            GenerateCombinationsHelper(results, min, max, currentValue, index + 1, maxValues, currentCombo, values);
        }
        else
        {
            results.Add((int[])currentCombo.Clone());
        }
    }
}

Edit

整数值仅用于演示。它可以是任何具有某种数值的对象（int, double, float， ETC...）

通常只有少数唯一值（大约 10 个），但总共可能有数千个项目。

将主调用切换为：

GenerateCombinationsHelper2(new List<int[]>(), 13, 17, 0, maxCounts, new int[3], values);

然后添加以下代码：

private void GenerateCombinationsHelper2(List<int[]> results, int min, int max, int index, int[] maxValues, int[] currentCombo, int[] values)
{
    int max_count = Math.Min((int)Math.Ceiling((double)max / values[index]), maxValues[index]);

    for(int count = 0; count <= max_count; count++)
    {
        currentCombo[index] = count;
        if(index < currentCombo.Length - 1)
        {
            GenerateCombinationsHelper2(results, min, max, index + 1, maxValues, currentCombo, values);
        }
        else
        {
            int sum = Sum(currentCombo, values);
            if(sum >= min && sum <= max)
            {
                int[] copy = new int[currentCombo.Length];
                Array.Copy(currentCombo, copy, copy.Length);
                results.Add(copy);
            }
        }
    }
}

private static int Sum(int[] combo, int[] values)
{
    int sum = 0;
    for(int i = 0; i < combo.Length; i++)
    {
        sum += combo[i] * values[i];
    }
    return sum;
}

它返回 5 个有效答案。