Cách tìm tổ hợp duy nhất có tổng bằng số 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 đang tìm thấy trên cây đệ quy. Hàm backtrack đi sâu vào đệ quy cho đến khi đạt mục tiêu, ngược lại quay lui khi target < 0. Tại bất kỳ thời điểm nào, nếu target bằng 0 thì thêm mảng ứng viên vào kết quả vì các giá trị trong mảng ứng viên cộng lại bằng target cho trước.

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

Ví dụ: số là 5, cần tìm các số tạo thành 5. Kết quả sẽ là "1,4", "2,3", "5". Từ đầu ra "014", "023", "05" có thể loại bỏ.

Ví dụ

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);
        }
    }
}

Kết quả

14 23 05

Giải thích: Tìm tất cả tổ hợp các số nguyên dương khác nhau có tổng bằng n=5. Kết quả bao gồm: 1+4, 2+3, và 5 (tự thân). Các tổ hợp chứa 0 được loại bỏ.