문제는 더 작고 단순한 "하위 문제"로 나눌 수 있으며 더 간단하고 더 작은 하위 문제로 나눌 수 있습니다. 우리는 각각의 모든 숫자를 하나씩 가져와서 모든 숫자에서 도달할 수 있는 모든 n개의 숫자를 세고 지도를 사용하여 모든 숫자에서 도달할 수 있는 숫자의 매핑을 저장합니다. 숫자가 n자리가 되면 개수를 업데이트합니다.
예시
using System; using System.Collections.Generic; namespace ConsoleApplication{ public class BackTracking{ private string GetKeyPadValueBasedOnInput(string digit){ Dictionary keypad = new Dictionary(); keypad.Add("2", "abc"); keypad.Add("3", "def"); keypad.Add("4", "ghi"); keypad.Add("5", "jkl"); keypad.Add("6", "mno"); keypad.Add("7", "pqrs"); keypad.Add("8", "tuv"); keypad.Add("9", "wxyz"); return keypad.GetValueOrDefault(digit); } public void FindSequence(string currentList, string digits, List output){ if (digits.Length == 0){ output.Add(currentList); return; } else{ string digit = digits.Substring(0, 1); string letters = GetKeyPadValueBasedOnInput(digit); for (int i = 0; i < letters.Length; i++){ char letter = GetCHarFromString(letters, i); FindSequence(currentList + letter, digits.Substring(1), output); } } } private char GetCHarFromString(string letters, int value){ char[] charArr = letters.ToCharArray(); return charArr[value]; } } class Program{ static void Main(string[] args){ BackTracking b = new BackTracking(); List<string> output = new List<string>(); b.FindSequence("", "34", output); foreach (var item in output){ Console.WriteLine(item); } } } }
출력
dg dh di eg eh ei fg fh fi