昨天提到解決Backtracking 問題的三要素，今天要繼續利用他們來解決一些很常出現的Backtracking Problem。

Leetcode 46. Permutations

題目敘述：有一個input array，裡面的元素皆是整數，且值不重複。找出所有的排列的解。

Example：

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

分析：

• 選擇（Choose）：選取出input array中的某個數字，並且存放到solution array中
• 目標（Goal）：當solution array的長度達到和input array一樣時，此為其中一種解，記錄下來。
• 限制（Constriant）：當從input array中選擇某數時，不可以選已經在solution array中的數字。

Python 程式實作：

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        sol = []

        def backtrack():
            if len(sol) == len(nums):
                res.append(sol.copy())
                return
            
            for n in nums:
                # constraint: can't choose value already in sol
                if n not in sol:
                    sol.append(n)
                    backtrack()
                    sol.pop()
        
        backtrack()
        return res

Follow Up Leetcode 47. Permutations II

題目敘述：input array中的數字可能有重複的，return 所有unique 的排列。

Example：

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]

分析：我們需要去考慮到重複排列的問題，如果使用解決上一題的程式碼會得到兩個[1,1,2]：如果利用決策樹（decision tree）來可視化程式的選擇過程便可知道哪裡有問題。決策樹從root可以選擇1, 1, 2，這會造成部分路徑重複。

所以我們的限制（constraint）就是要限縮決策樹可以選擇的路徑。要實現這個目的我們可以用hash table 先紀錄input array 中每個數字出現的頻率。之後再做選擇時，我們是根據hash table 的key 和他們殘存的次數來規劃路境。

Python 程式實作：

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        sol = []
        table = {}
        for n in nums:
            table[n] = 1 + table.get(n, 0)

        def backtrack():
            if len(sol) == len(nums):
                res.append(sol.copy())
                return
            
            for key in table:
                if table[key] >= 1:
                    sol.append(key)
                    table[key] -= 1
                    backtrack()
                    table[key] += 1
                    sol.pop()
        
        backtrack()
        return res

Leetcode 22. Generate Parentheses

有n對左右括弧，找出所有可以形成有效括弧的組合。所謂的「有效」的括弧，代表所有的左右括弧是數量一致並且對稱的。從左到右看過去，左括弧一定會對應到一個右括弧。

Example：

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

分析：

• 目標（Goal）：一個solution裡面有n 個左括弧和n 個右括弧。
• 選擇（Choose）：加入左括弧或是右括弧到solution array中。
• 限制（Constraint）：左括弧需要去對應到一個右括弧。

關於「限制」，我們需要判斷何時加入左括弧何時加入右括弧來讓他們對應到彼此。

1. 在solution中的左括弧數量為0或是左括弧與右括弧數量一樣時（代表他們對應到該對應的括弧了），這時候只會加入左括弧，之後才能去和右括弧產生對應並且是有效的（valid）。
2. 如果solution中左括弧的數量比較多時，有兩種選擇：可以繼續增加左括弧直到數量到達n，或是增加右括弧直到數量到達solution中的左括弧或是到達n。

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        sol = []

        def dfs(left, right):
            if left == n and right == n:
                s = "".join(sol)
                res.append(s)
                return
            
            if left == 0 or left == right:
                sol.append("(")
                dfs(left + 1, right)
                sol.pop()
            elif left > right:
                # choose left or right
                if left < n:
                    sol.append("(")
                    dfs(left + 1, right)
                    sol.pop()
                
                sol.append(")")
                dfs(left, right + 1)
                sol.pop()
        
        dfs(0, 0)
        return res

後記：感覺就像在做筆記一樣，可以把已經知道技巧和pattern烙印在記憶中久一點。推薦在刷leetcode時，相同的題目至少要做個兩次。