Làm thế nào để tìm tổng hợp k duy nhất tương ứng với k tổng bằng cách sử dụng C #?

Tạo danh sách đầu ra để lưu trữ các trình tự hợp lệ, tạo danh sách hiện tại sẽ lưu trữ trình tự hiện tại được tìm thấy trong đường dẫn của cây đệ quy. Một hàm backtrack sẽ đi vào đệ quy cho đến khi đạt được mục tiêu, nếu không, nó sẽ quay lại giai đoạn trước khi mục tiêu trở nên nhỏ hơn 0. Tại bất kỳ thời điểm nào, nếu mục tiêu trở thành 0 thì hãy thêm mảng ứng viên vào kết quả như các giá trị trong mảng ứng viên phải được tổng hợp với mục tiêu đã cho.

Nếu đó không phải là trường hợp thì hãy thêm lần lượt các phần tử trong mảng ứng viên và tiếp tục đệ quy.

Giả sử, số là 5 và k là 2, vì vậy chúng ta cần tạo tổ hợp các số ở kích thước 2 tạo thành 5. Đầu ra sẽ là “1,4”, “2,3”.

Ví dụ

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
namespace ConsoleApplication{
   public class BackTracking{
      public void UniqueCombinationSumOfExactKNumbers(int n, int k){
         int[] array = new int[n];
         for (int i = 1; i < n; i++){
            array[i] = i;
         }
         List<int> currentList = new List<int>();
         List<List<int>> output = new List<List<int>>();
         UniqueCombinationSumOfExactKNumbers(array, n, k, 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 UniqueCombinationSumOfExactKNumbers(int[] array, int target, int countOfNumbers, int sum, int index, List<int> currentList, List<List<int>> output){
         if (sum == target){
            if (currentList.Count == countOfNumbers){
               List<int> newList = new List<int>();
               newList.AddRange(currentList);
               output.Add(newList);
               return;
            }
         }
         else if (sum > target){
            return;
         }
         else if (currentList.Count == countOfNumbers && sum != target){
            return;
         }
         else{
            for (int i = index; i < array.Length; i++){
               currentList.Add(array[i]);
               UniqueCombinationSumOfExactKNumbers(array, target, countOfNumbers, sum + array[i], i + 1, currentList, output);
               currentList.Remove(array[i]);
            }
         }
      }
   }
   class Program{
      static void Main(string[] args){
         BackTracking b = new BackTracking();
         b.UniqueCombinationSumOfExactKNumbers(5, 2);
      }
   }
}

Đầu ra

14
23