Cách tìm tổ hợp k số duy nhất có tổng bằng k cho trước bằng C#

Tạo danh sách đầu ra lưu các dãy hợp lệ, tạo danh sách hiện tại lưu dãy trên đường đệ quy. Hàm backtrack đệ quy cho đến khi đạt target, ngược lại quay lui khi target < 0. Khi target bằng 0, thêm mảng ứng viên vào kết quả nếu số phần tử đúng bằng k.

Ví dụ: số là 5 và k=2, cần tổ hợp 2 số có tổng 5. Kết quả: "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);
        }
    }
}

Kết quả

14 23

Giải thích: Tìm tổ hợp chính xác k=2 số nguyên dương khác nhau có tổng bằng n=5. Kết quả: 1+4 và 2+3. Tổ hợp {5} bị loại vì có 1 phần tử, không phải 2.