获取所有数字等于其给定总和的n位数字

Question

我怎样才能得到所有n位数字的总和等于给定的总和？我需要最快的解决方案，因为n可以等于9，总和可以等于1000。

我已经在下面实现了解决方案，但是它太慢了...

List<int> l = new List<int>();
void findNDigitNumsUtil(int n, int sum, char[] ou, int index)
{
    if (index > n || sum < 0)
        return;
    if (index == n)
    {
        if (sum == 0)
        {
            ou[index] = '\0';
            string s = new string(ou);
            l.Add(Int32.Parse(s));
        }

        return;
    }

    for (int i = 0; i <= 9; i++)
    {
        ou[index] = (char)(i + '0');
        findNDigitNumsUtil(n, sum - i, ou,
                                index + 1);

    }
}

void findNDigitNums(int n, int sum)
{
    char[] ou = new char[n + 1];
    for (int i = 1; i <= 9; i++)
    {
        ou[0] = (char)(i + '0');
        findNDigitNumsUtil(n, sum - i, ou, 1);
    }
}

Answer 1

我需要最快的解决方案

不，您需要一个足够快的解决方案。您可能甚至不愿意在定制硬件上花费一百万美元来获得最快的解决方案。

我怎样才能得到所有n位数字的总和等于给定的总和？

在这里，我将为您提供一个稍微不同的问题的解决方案：

n从0-9到的所有数字序列是sum什么？

这是不同的，因为它计数01并且10作为长度为2的序列的总和为1，但01不是两位数。

我将向您提示如何解决此较简单的问题。然后，您采用该解决方案，并将其适应于更困难的问题。

首先，您能解决一位数字问题吗？那很容易。如果n为0到9，则其数字总和为n的一位数字n，否则没有解决方案。

第二个：假设n>1。那么n加起来的- 位数字sum是：

• 0后跟所有n-1加起来的数字sum
• 1后跟所有n-1加起来的数字sum-1
• 2后跟所有n-1加起来的数字sum-2
• ...
• 9后跟所有n-1加起来的数字sum-9

编写解决该问题的实现，然后对其进行调整以解决您的问题。