如何从给定的数字 C# 中找到 sum 的唯一组合?

创建一个输出列表来存储有效序列,创建一个当前列表来存储在递归树的路径中找到的当前序列。一个回溯函数,将进入递归直到达到目标,否则,当目标小于 0 时,它应该回溯到前一阶段。 在任何时间点,如果目标变为 0,则将候选数组添加到结果中候选数组中的值必须与给定的目标相加。

如果不是这些情况,则将候选数组中的元素一一添加并递归前进。

假设数字是 5,所以我们需要找到组成 5 的数字。输出将是“1,4”、“2,3”、5。从输出 014、.023 和 05 可以丢弃

示例

using System;

using System.Collections.Generic;

using System.Text;

using System.Linq;

namespace ConsoleApplication{

   public class BackTracking{

      public void UniqueCombinationOfNumbersCorrespondsToSum(int n){

         int[] array = new int[n + 1];

         for (int i = 1; i <= n; i++){

            array[i] = i;}

            List<int> currentList = new List<int>();

            List<List<int>> output = new List<List<int>>();

            UniqueCombinationSum(array, n, 0, 0, currentList, output);

            foreach (var item in output){

               StringBuilder s = new StringBuilder();

               foreach (var item1 in item){

                  s.Append(item1.ToString());

               }

               Console.WriteLine(s);

               s = null;

            }

         }

         private void UniqueCombinationSum(int[] array, int target, int sum, int index, List<int> currentList, List<List<int>> output){

            if (sum == target){

               List<int> newList = new List<int>();

               newList.AddRange(currentList);

               output.Add(newList);

               return;

            }

            else if (sum > target){

               return;

            }

            else{

               for (int i = index; i < array.Length; i++){

                  currentList.Add(array[i]);

                  UniqueCombinationSum(array, target, sum + array[i], i + 1, currentList, output);

                  currentList.Remove(array[i]);

               }

            }

         }

      }

      class Program{

         static void Main(string[] args){

            BackTracking b = new BackTracking();

            b.UniqueCombinationOfNumbersCorrespondsToSum(5);

         }

      }  

   }

}

输出结果
14

23

05

以上是 如何从给定的数字 C# 中找到 sum 的唯一组合? 的全部内容, 来源链接: utcz.com/z/361830.html

回到顶部