วิธีหาการจัดหมู่ต่างๆ ของวงเล็บเปิดและปิดจากตัวเลข k ที่กำหนดโดยใช้ C#

สร้างฟังก์ชัน backtrack ที่อัปเดตสตริงปัจจุบันหากวงเล็บเปิดน้อยกว่า n หรือวงเล็บปิดน้อยกว่าวงเล็บเปิด เมื่อความยาวของสตริงปัจจุบันเท่ากับ 2*n ให้เพิ่มเข้าไปในอาร์เรย์ผลลัพธ์ สามารถติดตามได้ง่ายๆ โดยนับจำนวน { } ที่วางไว้ เราสามารถเริ่มวงเล็บเปิดได้หากยังมีเหลืออยู่ และสามารถเริ่มวงเล็บปิดได้หากไม่เกินจำนวนวงเล็บเปิด

ตัวอย่าง

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

namespace ConsoleApplication
{
    public class BackTracking
    {
        public void Brackets()
        {
            char[] arr = new char[4];
            FindSequence(arr, 0, 2, 0, 0);
        }

        private static void FindSequence(char[] arr, int index, int N, int openBracket, int closeBracket)
        {
            if (closeBracket == N)
            {
                StringBuilder s = new StringBuilder();
                for (int i = 0; i < arr.Length; i++)
                {
                    s.Append(arr[i]);
                }
                Console.WriteLine(s);
                s = null;
                return;
            }
            else
            {
                if (openBracket > closeBracket)
                {
                    arr[index] = '}';
                    FindSequence(arr, index + 1, N, openBracket, closeBracket + 1);
                }
                if (openBracket < N)
                {
                    arr[index] = '{';
                    FindSequence(arr, index + 1, N, openBracket + 1, closeBracket);
                }
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            BackTracking b = new BackTracking();
            b.Brackets();
        }
    }
}

ผลลัพธ์

{}{} {{}}