วิธีหาการจัดหมู่ k ตัวที่ไม่ซ้ำกันซึ่งผลรวมเท่ากับ k ด้วย C#

สร้างรายการผลลัพธ์เพื่อเก็บลำดับที่ถูกต้อง สร้างรายการปัจจุบันที่จะเก็บลำดับปัจจุบันที่พบในเส้นทางของต้นไม้ recursion ฟังก์ชัน backtrack ที่จะเข้าสู่ recursion จนกว่าจะบรรลุเป้าหมาย มิฉะนั้นจะ backtrack กลับไปขั้นตอนก่อนหน้าเมื่อ target น้อยกว่า 0 หาก target กลายเป็น 0 ให้เพิ่มอาร์เรย์ผู้สมัครเข้าไปในผลลัพธ์ เนื่องจากค่าในอาร์เรย์ผู้สมัครต้องรวมกันได้เท่ากับ target ที่กำหนด

หากไม่ใช่กรณีดังกล่าว ให้นำองค์ประกอบในอาร์เรย์ผู้สมัครมาเพิ่มทีละตัวและเรียก recursion ต่อไป

เช่น ตัวเลขคือ 5 และ k คือ 2 เราต้องสร้างการจัดหมู่ของตัวเลขขนาด 2 ที่รวมกันได้ 5 ผลลัพธ์จะเป็น "1,4", "2,3"

ตัวอย่าง

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 currentList = new List();
            List> output = new List>();
            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 currentList, List> output)
        {
            if (sum == target)
            {
                if (currentList.Count == countOfNumbers)
                {
                    List newList = new List();
                    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);
        }
    }
}

ผลลัพธ์

14 23