Cách tìm các tập con riêng biệt từ mảng cho trước bằng backtracking C#

Bài toán tập con riêng biệt cho ta các tổ hợp khác nhau từ mảng cho trước.

Khi target=2, từ mảng ta lấy tất cả tổ hợp tương ứng với số 2. Khi target=3, lấy tổ hợp tương ứng với số 3. Trong ví dụ mảng [1,2,3] và target=2, ta lấy tổ hợp 2 phần tử: "1,2", "2,3", "1,3".

Ví dụ

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace ConsoleApplication
{
    public class BackTracking
    {
        public void Subsets(int[] array)
        {
            List<int> currentList = new List<int>();
            List<string> results = new List<string>();
            BackTrackkingCombination(array, 2, 0, currentList, results);
            foreach (var item in results)
            {
                StringBuilder s = new StringBuilder();
                foreach (var item1 in item)
                {
                    s.Append(item1.ToString());
                }
                Console.WriteLine(s);
                s = null;
            }
        }

        public void BackTrackkingCombination(int[] array, int size, int startIndex, List<int> currentList, List<string> results)
        {
            if (currentList.Count == size)
            {
                StringBuilder s = new StringBuilder();
                foreach (var item in currentList)
                {
                    s.Append(item);
                }
                results.Add(s.ToString());
                return;
            }
            for (int i = startIndex; i < array.Length; i++)
            {
                currentList.Add(array[i]);
                BackTrackkingCombination(array, size, i + 1, currentList, results);
                currentList.Remove(array[i]);
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            BackTracking b = new BackTracking();
            int[] arrs = { 1, 2, 3 };
            b.Subsets(arrs);
        }
    }
}

Kết quả

12 13 23

Giải thích: Sinh tất cả tập con kích thước k=2 từ mảng [1,2,3]. Kết quả: {1,2}, {1,3}, {2,3}. Thuật toán backtracking duyệt tổ hợp không trùng lặp.