Let’s talk about Backtracking | Kyaw Zay Ya Lin Tun

Introduction

Backtracking ဆိုတာ recursive call တွေမှာ မသိမဖြစ်သိထားရမယ့် အကြောင်းအရာတစ်ခုပါ။ Backtracking သဘောကိုနားလည်ရင် tree/graph/dp သုံးရတဲ့ အဆင့်မြင့် algorithms တော်တော်များများကို နားလည်အသုံးပြုနိုင်ပါလိမ့်မယ်။ အနည်းဆုံးတော့ ဘယ်လိုအသုံးချရမလဲဆိုတဲ့ idea တော့ အနည်းနဲ့အများ ရလာမယ်ထင်ပါတယ်။

Prerequisite

Recursion

Why should you care about backtracking?

Backtracking ဆိုတာက brute force ကိုမှ ပိုပြီး efficient ဖြစ်တဲ့ brute force လို့ပြောလို့ရပါတယ်။ ပုစ္ဆာတစ်ခုမှာ ဖြစ်နိုင်ခြေတွေအားလုံးကို strategically စဥ်းစားပြီးအဖြေထုတ်သွားတာမျိုးပါ။ နောက်ဆက်ပြောမယ် article တွေကို လိုက်လုပ်နိုင်ဖို့ဆိုရင် backtracking သိဖို့လိုပါတယ်။ ရှေ့ recursion article မှာပြောခဲ့ပြီးသားအကြောင်းအရာတွေကို နားလည်ထားမှ backtracking ကို လိုက်လုပ်နိုင်ပါလိမ့်မယ်။

Backtracking in Action

ထုံးစံအတိုင်း ပုစ္ဆာလေးတစ်ပုဒ်နဲ့အရင် စကြည့်လိုက်ရအောင်။

https://www.geeksforgeeks.org/problems/power-set4302/1

Given a string S, find all the possible subsequences of the String in lexicographically-sorted order.

ဒါက ပုစ္ဆာမှာ အရေးကြီးတဲ့အချက်တွေကို bold လုပ်ပြထားတာပါ။ Subsequence ဆိုတဲ့သဘောက same order ဖြစ်ရပါမယ်။ ဆိုကြပါစို့။ String “abc” မှာ “ac” ဆိုတာက subsequence ဖြစ်ပါတယ်။ ဒါပေမယ့် “ca” ဆိုရင်တော့ subsequence မဟုတ်ပါဘူး။ Original string မှာပါတဲ့ order စဥ်အတိုင်းမဟုတ်လို့ပါ။ Subarray ဆိုတာရှိပါသေးတယ်။ Subarray ဆိုရင်တော့ contiguous ဖြစ်ရပါမယ်။ ဥပမာ “ab” ဆိုရင် subsequence လည်းဟုတ်တယ် subarray လည်းဟုတ်တယ်။ ဒါပေမယ့် “ac” ဆိုရင်တော့ subsequence ဟုတ်ပေမယ့် subarray မဟုတ်တော့ပါဘူး ကြားထဲက “b” မပါလာလို့ပါ။ ဒါလေးက အပိုအနေနဲ့ပြောပြတာပါ။

သူဥပမာပေးထားတဲ့ input/output ကို ကြည့်ရအောင်ပါ။ တစ်ကယ်လို့ string S က “abc” လို့ပေးလာခဲ့ရင် output က [“a”, “ab”, “abc”, “ac”, “b”, “bc”, “c”] ဆိုပြီးထွက်ပါမယ်။

Input: str = "abc"
Output: a ab abc ac b bc c
Explanation: There are 7 subsequences that can be formed from "abc"

ဒီလိုပုစ္ဆာမျိုးကို powerset ပုစ္ဆာလို့ခေါ်ပါတယ်။ Powerset ကို formally define လုပ်မယ်ဆိုရင်

A power set is the set of all possible subsets of a given set, including the empty set and the set itself. For a set with 𝑛 elements, its power set will contain 2^n subsets.

ဥပမာ string “ab” ကို {“a”, “b”} အနေနဲ့မြင်ကြည့်မယ်ဆိုရင် သူ့ရဲ့ powerset က 2² ဆိုတော့ 4 ခုထွက်မှာပါ။ ဘာကြောင့်လဲဆိုတော့ powerset မှာ empty set ရှိတာကိုး။ မြင်သာအောင်ပြရရင် ဒီလိုပေါ့။

original set = {"a", "b"}
subset = {"", "a", "b", "ab"}

အဲ့တော့ ကျွန်တော်တို့ သူ့ဥပမာအတိုင်းစဥ်းစားမယ်ဆိုရင် “abc” ဆိုတော့ တစ်ကယ်က 2³ ဖြစ်ပြီး 8 ခုထွက်ရမှာပေါ့။ ဒါပေမယ့် သူက empty set “” ကို မယူတော့ 2³ - 1 ဖြစ်ပြီး 7 ခုထွက်လာတာဖြစ်ပါတယ်။ ဒါဆိုရင် ကျွန်တော်တို့ powerset သဘောတရားအတိုင်း empty set ကိုပါယူပြီး စဥ်းစားကြည့်ရအောင်။

“ab” နဲ့စစဥ်းစားကြည့်မယ်။ လွယ်အောင်လို့။ အဲ့တော့ စစချင်းက empty “” ဖြစ်နေမယ်။ အဲ့ကနေမှ possible ways က နှစ်ခုထွက်တယ်။ ပထမတစ်ခုက string “ab” ထဲက ပထမကောင်ဖြစ်တဲ့ “a” ကို ယူပြီး ခုနက empty “” နဲ့ပေါင်းလို့ရတယ် ဒါက ပထမ ဖြစ်နိုင်ချေ။ ဒုတိယက “a” ကိုမယူဘဲ လက်ရှိ ရှိပြီးသား empty “” အတိုင်းပဲထားလို့လည်းရတယ်။ Empty ကို မြင်သာအောင် “_” နဲ့ပြပါမယ်။

ဒီ ဖြစ်နိုင်တဲ့ နည်းလမ်းနှစ်ခုကိုအခြေတည်ပြီးတော့ decision tree တစ်ခု ဆွဲကြည့်ရအောင်။ Empty string “” ကနေ ပထမ possibility ဖြစ်တဲ့ “” ကို “a” နဲ့ပေါင်းပြီး “a” ထွက်တာရယ် ဒုတိယ possiblity ဖြစ်တဲ့ ရှိပြီးသား “” အတိုင်းထားတာရယ်ကို အရင်ကြည့်ပါမယ်။

string = a b
         ^
                "_"
               /   \
             "a"   "_"

ဆိုတော့ ကျွန်တော်တို့ “a” ကိုသုံးပြီးသွားပြီ။ ဘာကျန်လဲဆိုတော့ “b” ကျန်တယ်။ “b” ကိုဆက်စဥ်းစားဖို့ရာ အပေါ်မှာ “a” နဲ့ “_” ဆိုပြီး leaf node နှစ်ခုရှိတယ်။ အရင်ဆုံး left most node “a” ကနေစပြီး ညာဘက်ကို တစ်ခုချင်း စဥ်းစားသွားရအောင်။ အဲ့တော့ “a” ကနေ “b” နဲ့ပေါင်းမလား ဒါကတစ်နည်း ဒါမှမဟုတ် သူ့ချည်းပဲနေမလား (“a” အတိုင်းပဲနေမလား) ဒါကဒုတိယတစ်နည်း ဒီနှစ်ခုကို tree ထဲထည့်ဆွဲကြည့်ရအောင်။

string = a b
           ^
               "_"
              /   \
            "a"    "_"
            /  \     
          "ab" "a"

အဲ့တော့ “a” အတွက်တော့ရပြီ နောက်ကျန်နေတဲ့ leaf node က “_” အတွက်ကျန်တယ်

“” ကရော “b” နဲ့ပေါင်းမယ် ဒါမှမဟုတ် သူ့ချည်း “” အနေနဲ့နေမယ်။ ဒါကိုလည်းထပ်ထည့်ဆွဲလိုက်ရအောင်

string = a b
           ^
                 "_"
              /       \
            "a"       "_"
            /  \      /  \
          "ab" "a"   "b" "_"

ဒီအချိန်ကျတော့ original string ထဲက a ရော b ပါ သုံးပြီးသွားပြီဖြစ်တဲ့အတွက် ထပ်ထည့်လို့မရတော့ဘူး။ ဒါဆိုရင် possible subsequences တွေက “ab”, “a”, “b”, “” ဆိုပြီး ထွက်လာတယ်။ အဲ့ထဲကမှ empty “_” ကိုဖယ်လိုက်တော့ သုံးခုပဲကျန်တာပေါ့။

ပုစ္ဆာမှာ “c” ထပ်ထည့်ကြည့်ရအောင် ဒါဆို “abc” ဖြစ်တဲ့အတွက် ကျွန်တော်တို့ decision tree ကိုဆက်ဖြည့်ဆွဲကြည့်ရင် ဒီလိုထွက်ပါမယ်။

string = a b c
             ^
                    "_"
             /              \
            "a"             "_"
         /      \        /       \
       "ab"     "a"     "b"       "_"
       /  \    /   \    /  \     /  \
   "abc" "ab" "ac" "a" "bc" "b" "c" "_"

အပေါ်မှာလည်းရှင်းပြပြီးသားဆိုတော့ ဒီတစ်ခါ ဘယ်ကနေညာကို မြန်မြန်လေးရှင်းကြည့်ပါမယ်။

ပထမဆုံး leaf node “ab” ကနေ “c” ပေါင်းတော့ “abc”၊ မပေါင်းဘဲသူ့အတိုင်းနေတော့ “ab” ဆိုပြီးထွက်ပါတယ်။

ဆက်ပြီး leaf node “a” ကို “c” ပေါင်းတော့ “ac”, သူ့ချည်းနေတော့ “a” ဆိိုပြီးထွက်ပါတယ်။

တစ်ခါ “b” ကို “c” ပေါင်းတော့ “bc”, သူ့ချည်းနေတော့ “b” ဆိုပြီးထွက်ပါတယ်။

နောက်ဆုံးကျန်တဲ့ “” ကို “c” ပေါင်းတော့ “c”, သူ့ချည်းနေတော့ “” ဆိုပြီးထွက်ပါတယ်။

String ထဲမှာ သုံးစရာ character လည်းမကျန်တော့တဲ့အတွက် ဒီနေရာမှာ base case ဖြစ်ပါမယ်။ ရှေ့က article ကို ဖတ်ထားတယ်ဆိုရင် စဥ်းစားရမယ့် လေးချက်ကို မှတ်မိမှာပါ။ ထပ်ဆောင်းပြောချင်တာက အခုလို possible states တွေအားလုံးကို represent လုပ်တဲ့ tree မျိုးကို state-space tree လို့လဲခေါ်ပါတယ် (ဒီအတိုင်းပြောပြတာပါ)။

func allPossibleStrings(of s: String) -> [String] {
  // TODO: Implement
}

ဒါက function အခွံပါ။ Recursion လုပ်ဖို့အတွက် helper function တစ်ခုထပ်ရေးလိုက်ပါမယ်။

func helper() {
}

အပေါ်က recursive tree ကို ကြည့်ရင် လက်ရှိ ဘယ် character ကိုသုံးနေသလဲဆိုတာကို သိမှရပါမယ်။ ဒါဆိုရင် အနည်းဆုံး original string (char array) နဲ့ လက်ရှိ ဘယ် index ကို process လုပ််နေလဲဆိုတာ သိရပါမယ်။ အပေါ်က recursive tree မှာ စစချင်း root node က “” ပါ။ အဲ့ “” ကိုမှ include/not include ဆိုပြီး decision ခွဲတာပါ။ ဒါဆိုရင် “_” ထည့်ပေးဖို့အတွက် နောက်ထပ် parameter တစ်ခုလိုပါမယ်။

func helper(_ chars: [Character], _ current: String, _ index: Int) {
}

အဲ့တော့ ကျွန်တော်တို့ဘာကို return ပြန်မလဲ ဆက်စဥ်းစားရအောင်။ မေးခွန်းက string array ကို return ပြန်ခိုင်းတာ။ ဒါဆိုရင် ကျွန်တော်တို့ helper က လည်း [String] ကို return ပြန်သင့်တာပေါ့။

func helper(_ chars: [Character], _ current: String, _ index: Int) -> [String] {
}

Base case က အပေါ်မှာ စဥ်းစားပြီးပြီ။ String ထဲမှာ သုံးစရာမကျန်တော့ရင် base case ကို ရောက်မှာပါ။ Base case ကိုရောက်ရင် ဘာပြန်မလဲ? Recursive tree အရဆိုရင် လက်ရှိရောက်နေတဲ့ leaf node ကို ပြန်ရပါမယ်။ ဒါဆိုရင် current string ကို [String] အနေနဲ့ပြန်ထည့်ပေးလိုက်ရင် ပြီးတာပါပဲ။

func helper(_ chars: [Character], _ current: String, _ index: Int) -> [String] {
  if index == chars.count {
    return [current]
  }
}

အပေါ်က recursive tree မှာ decision နှစ်ခုခွဲထွက်တယ်လို့ ပြောခဲ့ပါတယ်။ ပထမ decision က လက်ရှိ index က character ကို current string ထဲကို ပေါင်းထည့်တာ။ အဲ့တာကို အပေါ်က function ထဲထည့်မယ်ဆိုရင် ဒီလိုရပါတယ်။

helper(chars, current + String(chars[index]), index + 1)

ဒုတိယ decision ဖြစ်တဲ့ သူ့ချည်းနေတာကိုရေးကြည့်ရင် ဒီလိုဖြစ်ပါမယ်။ Index ကတော့ အမြဲ 1 increment ပေးနေရမှာပါ။ ဒါမှသာ နောက်ဆုံး base case ကို ရောက်မှာဖြစ်ပါတယ်။

helper(chars, current, index + 1)

Include လုပ်တာရယ် သူ့ချည်းနေတာရယ် နှစ်ခုကိုပေါင်းလိုက်ရင် decision branch တစ်ခုအတွက် possible sub sequences တွေရလာမှာဖြစ်ပါတယ်။ နားမလည်ရင် recursive tree (decision tree) ကို ပြန်ကြည့်ပါ။ Code ကို အပြည့်အစုံရေးလိုက်ရင် ဒီလိုဖြစ်ပါမယ်။

func allPossibleStrings(of s: String) -> [String] {
  return helper(Array(s), "", 0)
}

func helper(_ chars: [Character], _ current: String, _ index: Int) -> [String] {
  if index == chars.count {
    return [current]
  }
  
  let withChar = helper(chars, current + String(chars[index]), index + 1)
  
  let withoutChar = helper(chars, current, index + 1)
  
  return withChar + withoutChar
}

အပေါ်က code ကို “abc” နဲ့ run ကြည့်ရင် recursive tree ထဲက leaf node အတိုင်း တသဝေမတိမ်းထွက်တာကို တွေ့ရပါလိမ့်မယ်။ ကျွန်တော်တို့က “” ကို final result က ဖြုတ်ရမှာမို့ drop last လုပ်လိုက်ရင်ရပါတယ်။ ကျွန်တော်ကတော့ ပိုစိတ်ချရအောင် order ပြောင်းသွားလဲ “” မပါလာအောင် ဒီလိုရေးလိုက်ပါတယ်။

func allPossibleStrings(of s: String) -> [String] {
  helper(Array(s), "", 0)
    .filter({ !$0.trimmingCharacters(in: .whitespaces).isEmpty })
}

အဲ့တော့ မေးစရာတစ်ခုရှိတယ်။ ပြောတော့ backtracking ဆိုပြီး ဘယ့်နှယ့် recursion ဖြစ်နေရတာလဲပေါ့။ ဒါက recursion ပုစ္ဆာပါ။ ဒါပေမယ့် backtrack လုပ်သွားတဲ့နေရာရှိပါတယ်။ အဲ့တာကို မမြင်သေးရင် မြင်အောင်ကြည့်တတ်ဖို့ပါ။ ဘယ်နေရာ backtrack လုပ်သွားသလဲတဲ့။ “abc” tree ကိုပြန်ကြည့်ပါ။

                    "_"
             /              \
            "a"             "_"
         /      \        /       \
       "ab"     "a"     "b"       "_"
       /  \    /   \    /  \     /  \
   "abc" "ab" "ac" "a" "bc" "b" "c" "_"

Program က ဘယ်လို run သွားလဲဆိုတော့

"_" -> "a" -> "ab" -> "abc"

အဲ့မှာ base case ရောက်ပြီး [“abc”] ကို return ပြန်ပါတယ်။ နောက်ဆုံး stack frame ကို pop ပြီးတော့ ဘယ်ရောက်သလဲဆိုတော့ “ab” ကို ရောက်တာပါ။ “ab” ကိုရောက်တော့ သူ့ချည်းနေမယ်ဆိုတော့ [“ab”] ထွက်တာပါ။

အဲ့လို stack frame ကနေ pop လုပ်ပြီးတော့မှ အပေါ်ပြန်တက်လာရင်း ထပ်ပြီး branch ခွဲတာကို backtrack လုပ်တယ်လို့ခေါ်တာပါ။ ဥပမာ ဝင်္ကပါတစ်ခုမှာ လမ်း A, B, C ရှိတယ်ဆိုရင် C မှာလမ်းဆုံးရင် B ကိုနောက်ပြန်ဆုတ်ပြီး B ကနေ သွားလို့ရသေးတဲ့လမ်းရှိလားကြည့် မရှိဘူးဆိရင် အစ A ကိုပြန်သွားပြီး B မဟုတ်တဲ့နောက်တစ်လမ်းကိုရွေးတာမျိုး အဲ့လို ကိုယ်လာခဲ့တဲ့လမ်းကို အဖြေမှန်မတွေ့မချင်း တစ်ဆင့်ချင်းပြန်ဆုတ်သွားပြီး branch ထပ်ခွဲတာကို bracktracking လုပ်တယ်လို့ခေါ်တာဖြစ်ပါတယ်။ ပိုမြင်သာတဲ့ ပုစ္ဆာနောက်တစ်ပုဒ်ကိုသွားလိုက်ရအောင်။

Given a non-negative integer n, find all n-letter words composed by ‘က’ and ‘မ’, return them in a list of strings in lexicographical order.

မူရင်းပုစ္ဆာကိုဖျောက်ချင်လို့မဟုတ်ပါဘူး။ မြန်မာတွေအတွက် မြန်မာလိုရေးတာဆိုတော့ နည်းနည်းလေး ပျော်ဖို့ကောင်းအောင် မြန်မာမှုပြုလိုက်ရတာပါ။ Original ကတော့ “a” နဲ့ “b” ကိုသုံးခိုင်းတာပါ။ N letter word တွေကို “က” နဲ့ “မ” သုံးပြီး generate ထုတ်ခိုင်းတာဖြစ်ပါတယ်။ ဥပမာ n က 2 ဖြစ်ခဲ့ရင် possible words တွေက [“ကက”, “ကမ”, “မက”, မမ”] ဆိုပြီး လေးလုံးထွက်မယ်။ တစ်ကယ်လို့ n က 3 ဖြစ်ခဲ့ရင် possible words တွေက [“ကကက”, “ကကမ”, “ကမက”, “ကမမ”, “မကက”, “မကမ”, “မမက”, “မမမ”] ဆိုပြီး ထွက်ရပါမယ်။

Function အခွံအရင်ပြပါမယ်။

func generateLetterCombination(of n: Int) -> [String] {

}

ဒီလိုမျိုး combinatorial problem မျိုးကိုဖြေရှင်းမယ်ဆိုရင် recrusion က အသက်ပါပဲ။ ဒါကတော့ နောက်ပိုင်း ဘယ်လိုပြသနာဆိုရင် ဘယ်လိုဟာနဲ့ရှင်းရမလဲဆိုတာမျိုးရေးမှ စုပြီးရေးပြပါဦးမယ်။ ဒီမှာကတော့ backtracking ကို နားလည်အောင် ကြည့်ကြဦးစို့။ အဲ့တော့ အရင်ဆုံး n က 1 ဆိုရင် ဘယ်လိုဖြစ်မလဲဆိုတာကို စဥ်းစားကြည့်ရအောင်။

n = 1
 
  ""
 /  \
က   မ

မြင်တဲ့အတိုင်း “က”, “မ” နှစ်လုံးပဲထွက်စရာရှိပါတယ်။ n က 2 ဆိုရင်ရော?

n က နှစ်လုံးဖြစ်ခဲ့ရင် ပထမတစ်လုံးက “က” နဲ့ “မ” နှစ်လုံးထဲကတစ်လုံးနဲ့စပါမယ်။ ဒုတိယတစ်လုံးကလည်း “က” နဲ့ “မ” နှစ်လုံးထဲက တစ်လုံးနဲ့ဆုံးရပါမယ်။ ဒါက recursive tree (ဒီနေရာမှာတော့ state-space tree ပေါ့) အနေနဲ့ ချဆွဲကြည့်ရင် ဒီလိုတွေ့ရပါမယ်။

n = 2

        "" 
     /      \
    က_     မ_
   /  \     / \
 ကက ကမ  မက မမ

နောက်ဆုံး လေးလုံးထွက်လာပါတယ်။ n ကသုံးလုံးဆိုရင် ၈ လုံးထွက်မှာဖြစ်ပါတယ်။ ဒါကိုလေ့လာကြည့်ရင် ဘာကိုသိနိုင်သလဲဆိုတော့ “” ကနေ branch တစ်ခါခွဲမယ်ဆိုရင် possiblity ၂ ခုရှိပါတယ်။ Branch က n ကြိမ် ခွဲရမယ်ဆိုတော့ 2^n (2 power n) လုံးထွက်တာဖြစ်ပါတယ်။ ပိုပြီးမြင်သာအောင် n ကို 3 ထားပြီး စဥ်းစားကြည့်ပါမယ်။

n = 3
                   ""
              /          \
           က__           မ__

သုံးလုံးမှာ ပထမတစ်လုံစီရပါပြီ။ ဒုတိယအလုံးကိုသွားပါမယ်။

n = 3
                       ""
              /                  \
           က__                  မ__
       /       \              /      \
    ကက_      ကမ_          မက_    မမ_

ဒုတိယနေရာအတွက်လည်းရပါပြီ။

n = 3
                       ""
              /                  \
           က__                  မ__
       /       \              /      \
    ကက_      ကမ_          မက_    မမ_
     / \         / \        / \       / \
 ကကက ကကမ ကမက ကမမ မကက မကမ မမက မမမ

နောက်ဆုံး တတိယနေရာအတွက်ပါ ထွက်သွားပါပြီ။

အဲ့တော့ backtracking ကဘယ်နေရာလုပ်နေတာတဲ့လဲ? အပေါ်က recursive tree ကို ကြည့်ရအောင်။ အပေါ်က tree ကိုကြည့်မယ်ဆိုရင် “” ကနေ “က__”, n က ၃ ဆိုတော့ နောက်ထပ် “က” တစ်လုံးထပ်ကပ်တော့ “ကက_”, နောက်တစ်လုံးထပ်ကပ်တော့ “ကကက” ဆိုပြီး တစ်လုံးထွက်ပါပြီ။ အောက်ကပုံအတိုင်းဖြစ်သွားပါပြီ။

“ကကက” ပြီးတော့ အပေါ်ကိုပြန်တက် (backtrack) တဲ့အခါ “ကက_” ကိုပြန်ရောက်ပါတယ်။ “က” သုံးပြီး “မ” ကမသုံးရသေးတဲ့အတွက် လက်ရှိ “ကက_” ကို “မ” ထပ်ကပ်ပါတယ်။ “ကကမ” ဆိုပြီး နှစ်လုံးထွက်ပါပြီ။

ဒီအခါကျတော့ “ကကက” ရော “ကကမ”ရောပြီးပြီဖြစ်တဲ့အတွက် “ကက_” branch ရဲ့ တာဝန်ပြီးပါပြီ။ ဒါဆိုရင် “က__” ကို ပြန်ပြီး backtrack လုပ်ပါတယ်။ တစ်နည်းပြောရရင် recursive stack frame ထဲကနေ pop လုပ်လိုက်တာပါပဲ။ Pop တဲ့အချိန် ရှိနေတဲ့ source of truth (in this case “က__”) ကိုမှ ကျွန်တော်တို့က ကျန်သေးတဲ့ “မ” ထပ်ကပ်လိုက်ပါတယ်။ ဒါဆို အပေါ်ကအတိုင်း “ကမ_” ဖြစ်လာပါတယ်။

                      ""
              /                  
           က__               
       /       \              
    ကက_      ကမ_          
     / \    
 ကကက ကကမ

“ကမ_” မှာ တစ်လုံးလိုတဲ့အတွက် “က” ကပ်လိုက်တော့ “ကမက” ဆိုပြီး တတိယအလုံးထွက်လာပြန်ပါတယ်။

                     ""
              /                  
           က__               
       /       \              
    ကက_      ကမ_          
     / \         / 
 ကကက ကကမ ကမက

သုံးလုံးပြည့်ပြီဆိုတော့ “ကမ_” ကိုပြန်ပြီး back track လုပ်ပါမယ်။ လုပ်တဲ့အခါမှာ “က” က သုံးပြီးသားဖြစ်တော့ “ကမ_” ကို “မ” ပဲထပ်ကပ်လို့ရပါမယ်။ အဲ့လိုနဲ့ စတုတ္ထအလုံး “ကမမ” ဆိုပြီးရလာပါတယ်။

                    ""
              /                  
           က__               
       /       \              
    ကက_      ကမ_          
     / \         / \
 ကကက ကကမ ကမက ကမမ

အခုဆိုရင် လေးလုံးမြောက်ရသွားပြီဖြစ်လို့ “ကမ_” branch က ဖြစ်နိုင်ချေနှစ်ခုလုံး ပြည့်စုံသွားပါပြီ။ “ကမ__” ကပြီးသွားတဲ့အခါ ခုနက ပြီးသွားတဲ့ “ကက_” နဲ့ အခု ပြီးသွားတဲ့ “ကမ_” နှစ်ခုလုံးပြည့်စုံသွားတဲ့အတွက် “က__” ကလည်း ဘယ်ဘက်အခြမ်းပြည့်စုံသွားပါပြီ။ နောက်ဆက်လာမှာက “” ကို “မ” ကပ်ပြီး “မ__”, တစ်ခါ နှစ်လုံးလိုသေးတော့ “က” တွေကပ်ပြီး ဘယ်ဘက်ကိုဆက်ဆင်းသွားတော့ “မက_”, “မကက” ဆိုပြီး ဆက်ထွက်လာမှာပါ။

                      ""
              /                  \
           က__                  မ__
       /       \              /
    ကက_      ကမ_          မက_
     / \         / \        /
 ကကက ကကမ ကမက ကမမ မကက

ညာဘက်အခြမ်းကိုတော့ ဆက်မရေးပြတော့ပါဘူး။ ရှည်မှာစိုးလို့ပါ။ ဒီလောက်ဆို backtracking ကို မြင်ပြီလို့ထင်ပါတယ်။ State-space tree ရဲ့ ဘယ်ဘက်အစွန်ဆုံး base case အထိရောက်အောင်ဆင်းပြီးတော့မှ အပေါ်တစ်ဆင့်ပြန်တက် ကျန်သေးတဲ့ node တွေကို အဆုံးထိရောက်အောင်ဆက်သွား အပေါ်ပြန်တက် ဒီလိုအပေါ်ပြန်တက်တာကို backtrack လုပ်တာလို့ခေါ်ပါတယ်။ Backtrack လုပ်တာ ဘာကောင်းသလဲဆိုတော့ မြင်ကြတဲ့အတိုင်း possible case တွေအကုန်လုံးကို ဇကာနဲ့စစ်ချသလို အကုန်ထွက်သွားပါတယ်။ အပေါ်ကသဘောတရားကိုနားလည်ရင် ကိုယ့်ဘာသာ ညာဘက်အခြမ်း “မ__” ရဲ့ node တွေကို ချဆွဲကြည့်ပါ။

Code ရေးကြည့်ပါမယ်။

func generateLetterCombination(of n: Int) -> [String] {
  return helper("", n)
}

private func helper(_ s: String, _ n: Int) -> [String] {
  // When the string reaches length n, return it as a single-element array
  if s.count == n {
    return [s]
  }
  
  // Recursive case that adds 'က' and 'ခ' to the string and combine results
  let with_က = helper(s + "က", n)
  let with_ခ = helper(s + "ခ", n)
  
  return with_က + with_ခ
}

ရှေ့မှာလည်း recursive function ရေးရင် စဥ်းစားရမယ့်အကြောင်းတွေ ရေးတန်သလောက် ရေးပြီးဖြစ်တဲ့အတွက် အသေးစိတ်မရှင်းပြတော့ပါဘူး။ ကျွန်တော့် code မှာ recursive func ရေးဖို့ စဥ်းစားရမယ့်လေးချက် ပါသလား? ဘယ်လိုနေရာတွေမှာ အဲ့အချက်တွေကိုသုံးထားသလဲ? ဘာကြောင့်သုံးထားသလဲ? ကိုယ့်ဘာသမေးခွန်းထုတ်ပြီး ဖြေနိုင်လားကြည့်ပါ။ မဖြေနိုင်တဲ့သူရှိရင် comment ရေးခဲ့လို့ရပါတယ်။ ကျွန်တော်ပြန်ရှင်းပြပေးပါ့မယ်။

ဒီအထိနားလည်ပြီဆိုရင် ပုစ္ဆာတစ်ပုဒ်ပေးပါမယ်။ ဒီ ပုစ္ဆာ ကို ကိုယ့်ဘာသာ ဖြေရှင်းကြည့်ပါ။

https://www.geeksforgeeks.org/problems/permutations-of-a-given-string-1587115620/1?sortBy=submissions&category%5B%5D=Recursion&page=2

ကျွန်တော်အပေါ်ကရှင်းပြထားတဲ့ ပုစ္ဆာတွေနဲ့ အမျိုးအစားတူပါတယ်။

Summary

Recursion က ခက်ပါတယ်။ Backtracking ကပိုပြီးသိမ်မွေ့တဲ့အတွက် မြင်ဖို့ပိုခက်ပါတယ်။ ကျွန်တော့်ရည်ရွယ်ချက်ကတော့ backtracking ကိုယ့်ဘာသာမစဥ်းစားနိုင်သေးခင်မှာ အရင်ဆုံး backtracking လုပ်ထားတဲ့ code ကို နားလည်အောင်ဖတ်နိုင်ဖို့ဖြစ်ပါတယ်။ ကျွန်တော်တို့တွေက စာမရေးတတ်ခင် စာဖတ်အရင်သင်ရပါတယ်။ ဒီသဘောပါပဲ။

Recursion မှာတုန်းက recrusive tree ဆွဲပြီး visualise လုပ်ဖို့ပြောခဲ့ပါတယ်။ Backtracking က recursive tree ဆွဲဖို့ ပိုလို့တောင်လိုပါသေးတယ်။ ကျွန်တော်ကိုယ်တိုင်လည်း backtracking ပုစ္ဆာတွေဆိုရင် အလွယ်ကူဆုံး minimal အဖြစ်ဆုံး recursive tree တစ်ခုဆွဲကြည့်ပြီးမှသာ အဲ့ tree ကိုကြည့်ပြီးတော့မှ ဘယ်ကစ code ရေးရမလဲ ပေါ်တာဖြစ်တဲ့အတွက် ကိုယ့်ဘာသာ recursive tree ချဆွဲတတ်ဖို့ သိပ်ကိုအရေးကြီးပါတယ်။

နောက်အပိုင်းကတော့ algorithm ကိုခဏနားပြီး recursion ရော backtracking ရောရပြီဖြစ်တဲ့အတွက် tree data structure အကြောင်းကိုဆက်ပြောသွားမှာဖြစ်ပါတယ်။

Until next time!