-1

如何获得所有位数之和等于给定总和的 n 位数？我需要最快的解决方案，因为 n 可以等于 9，而 sum 可以等于 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);
    }
}
4

2 回答 2

5

我需要最快的解决方案

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

如何获得所有位数之和等于给定总和的 n 位数？

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

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

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

我会告诉你如何解决这个更简单的问题。然后，您采用该解决方案并使其适应您更难的问题。

首先，你能解决一位数字的问题吗？这很容易。n如果 n 为 0 到 9，则其数字之和为一位数，n否则无解。

第二：假设 n > 1。那么n和为的 -digit 数字sum是：

  • 0后面n-1是总和为的所有数字sum
  • 1后面n-1是总和为的所有数字sum-1
  • 2后面n-1是总和为的所有数字sum-2
  • ...
  • 9后面n-1是总和为的所有数字sum-9

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

于 2018-06-18T18:18:04.567 回答
0

You can treat n-digit number as an array of n digits. Then you can increment a particular number to the next number that also adds up to the sum. Stepping through all the next answers, you have generated all possible combinations.

Using a generator to yield each n-digit combination as an IEnumerable<int> (in fact, an int[]), you start with the "smallest" n-digit combination that yields the sum, and go through each one.

IEnumerable<IEnumerable<int>> DigitsToSum(int n, int sum) {
    if (sum > 9 * n)
        yield return Enumerable.Empty<int>();
    else {
        var ans = new int[n];

        void distribute(int wsum, int downto) {
            for (var j1 = n - 1; j1 > downto; --j1) {
                if (wsum > 9) {
                    ans[j1] = 9;
                    wsum -= 9;
                }
                else {
                    ans[j1] = wsum;
                    wsum = 0;
                }
            }
        }

        ans[0] = Math.Max(1, sum-9*(n-1));
        distribute(sum-ans[0], 0);

        bool nextAns() {
            var wsum = ans[n-1];
            for (var j1 = n - 2; j1 >= 0; --j1) {
                wsum += ans[j1];

                if (ans[j1] < Math.Min(9, wsum)) {
                    ++ans[j1];
                    distribute(wsum - ans[j1], j1);
                    return true;
                }
            }
            return false;
        }

        do {
            yield return ans;
        } while (nextAns());
    }
}

This is tremendously faster than my recursive double generator solution (somewhat like @EricLippert's suggestion) to iterate over all possibilities (e.g. using Count()).

You can put the digits back together to get a final numeric string for each number:

var ans = DigitsToSum(n, sum).Select(p => String.Join("", p));
于 2018-06-19T00:22:31.020 回答