加起來等于給定自然數的組合

在過去的一周里，我一直在努力解決這個非常棘手的問題:(我必須使用遞回找到總和為給定自然數的所有數字組合。除了“使用系統”之外，我不允許使用 LINQ 或其他任何東西"

例如，如果輸入為 7，則輸出應如下所示：

1   1   1   1   1   1   1
2   1   1   1   1   1
2   2   1   1   1
2   2   2   1
3   1   1   1   1
3   2   1   1
3   2   2
3   3   1
4   1   1   1
4   2   1
4   3
5   1   1
5   2
6   1

組合中的數字應按該順序準確列出，因此對于輸入 3，例如，輸出應完全如下：

1   1   1
2   1

對于 4 的輸入，輸出應如下所示：

1   1   1   1
2   1   1
2   2
3   1

對于每個新的組合串列，我們增加串列中的第一個數字，然后我們繼續前一個串列的剩余部分，直到總和與輸入相等。

在 1（包括 1）和輸入 - 1 之間只允許正數。

到目前為止，對于相同的給定輸入 7，我的代碼為我提供了以下輸出：

  1
   1   1   2
   1   1   1
   2   2   3
   1   1   1
   1   1   2
   2   1
   1   1   2
   2   2   1
   3   3   4
   1   1   1
   1   1   2
   1   1   1
   2   2   3
   2   1
   1   1   2
   1   1   1
   2   2   3
...

Can you please help me with some suggestions?

static string GenerateCombinations(int n)        
{
    string combinationList = "";

    for (int index = 1; index < n - 1; index  )
    {
        string intermediaryList = GenerateCombinations(n - index, index)   "   "   index;

        combinationList  = intermediaryList;
    }

    return combinationList   "\n";
}

static string GenerateCombinations(int n, int index)
{
    string combinationList = "";

    for (int i = 1; i < n - 1; i  )
    {
        if (i <= index)
        {
            string intermediaryList = GenerateCombinations(n)   "   "   index;

            combinationList  = intermediaryList;
        }
    }

    return combinationList;
}

static void Main()
{
    int n = Convert.ToInt32(Console.ReadLine());

    Console.WriteLine(GenerateCombinations(n));
}

uj5u.com熱心網友回復：

這是一個不使用集合（僅using System;）并按所需順序生成輸出的解決方案。

public static void PrintCombinations(int n)
{
    PrintRest("", 0, n, n - 1);
}

private static void PrintRest(string listStart, int startSum, int n, int max)
{
    for (int i = 1; i <= max; i  ) {
        string list = listStart.Length > 0
            ? listStart   "   "   i.ToString()
            : i.ToString();
        int sum = startSum   i;
        if (sum == n) {
            Console.WriteLine(list);
        } else if (sum < n) {
            PrintRest(list, sum, n, i);
        }
    }
}

你會稱它為

PrintCombinations(7);

它首先獲取所有可能的起始加法并呼叫自身來構造剩余的總和。直到當前點的組合作為字串引數傳遞listStart。它表示的總和作為 傳遞int startSum。目標總和為n。max是允許的最大總和。

uj5u.com熱心網友回復：

嘗試以下：

    class Program
    {
        static List<string> combinationList = new List<string>();
        const int SUM = 7;
        static void Main(string[] args)
        {
            List<int> numbers = new List<int>();
            GenerateCombinations(numbers, 0);
            combinationList.Sort();
            Console.WriteLine(string.Join("\n", combinationList));

            Console.ReadLine();
          
        }
        static void GenerateCombinations(List<int> numbers, int sum)
        {
            int start = 1;
            if (numbers.Count > 0) start = numbers[0]; 
                
            for (int i = start; i <= SUM; i  )
            {
                int newSum = sum   i;
                
                if (newSum > SUM) break;
                
                List<int> newList = new List<int>(numbers);
                newList.Insert(0,i);

                if (newSum == SUM)
                {
                    combinationList.Add(string.Join("   ", newList));
                    break;
                }
                else
                {
                    GenerateCombinations(newList, newSum);
                }

            }
        }
    }

uj5u.com熱心網友回復：

由于您正在尋找遞回解決方案，因此讓我們在沒有Linq和其他手段的情況下遞回地進行。

讓我們從基礎開始：當給定時0，我們有一個空的解決方案：

    private static int[][] Solutions(int value) {
      if (value <= 0)
        return new int[][] { new int[0] };

      //TODO: other cases for 1, 2, ... 
    }

是時候做下一步了：如果我們知道如何解決一些n - 1( n - 1 >= 0)，我們可以解決n如下：所有從m( m < n) 開始的解決方案都是形式

`m   solutions for n - m which uses m .. 1 only`

例如

6   1                      <- starts from 6, solves for 7 - 6 = 1, uses 6..1 only 
5   2                      ...
5   1   1
4   3
4   2   1
4   1   1   1              ... 
3   3   1                  <- starts from 3, solves for 7 - 3 = 4, uses 3..1 only
3   2   2                  <- starts from 3, solves for 7 - 3 = 4, uses 3..1 only 
3   2   1   1              <- starts from 3, solves for 7 - 3 = 4, uses 3..1 only
3   1   1   1   1          ...
2   2   2   1
2   2   1   1   1
2   1   1   1   1   1      ... 
1   1   1   1   1   1   1  <- starts from 1, solves for 7 - 1 = 6, uses 1..1 only

這個遞回可以編碼為

    private static int[][] Solutions(int value, int startWith = -1) {
      if (value <= 0)
        return new int[][] { new int[0] };

      if (startWith < 0)
        startWith = value - 1;

      List<int[]> solutions = new List<int[]>();

      for (int i = Math.Min(value, startWith); i >= 1; --i) 
        foreach (int[] solution in Solutions(value - i, i)) {
          int[] next = new int[solution.Length   1];

          Array.Copy(solution, 0, next, 1, solution.Length);
          next[0] = i;

          solutions.Add(next);
        }
      
      // Or just (if we are allow a bit of Linq)
      //   return solutions.ToArray();
      int[][] answer = new int[solutions.Count][];

      for (int i = 0; i < solutions.Count;   i)
        answer[i] = solutions[i];

      return answer;
    }

演示

var result = Solutions(7);

// A pinch of Linq for demonstration
string report = string.Join(Environment.NewLine, result
  .Select(solution => string.Join("   ", solution)));

Console.Write(report);

結果：

6   1
5   2
5   1   1
4   3
4   2   1
4   1   1   1
3   3   1
3   2   2
3   2   1   1
3   1   1   1   1
2   2   2   1
2   2   1   1   1
2   1   1   1   1   1
1   1   1   1   1   1   1

標籤：

上一篇：此代碼是否準確確定二叉搜索樹是否平衡？

下一篇：字串中的子字串搜索（Java）