여는 대괄호가 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(); } } }
출력
{}{} {{}}