LeetCode: Backtracking

    def subsets(nums):
        res = []
        
        def dfs_backtrack(start, path):

            # Process Root -> : record current subset first
            res.append(path[:]) 
            
            # Process -> Choices : decide which to include/exclude
            for i in range(start, len(nums)):

                # Build: include nums[i]
                path.append(nums[i])

                # Explore: recurse to next index
                dfs_backtrack(i + 1, path)

                # Backtrack: remove last element
                path.pop()
        
        dfs_backtrack(0, [])
        return res

    # Example: subsets([1,2,3]) -> [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

    def generateParenthesis(n):
        res = []
        
        def dfs_backtrack(open_count, close_count, path):
            
            # Process Root -> : check if sequence complete
            if len(path) == 2 * n:
                res.append("".join(path))
                return
            
            # Process -> Choices : add '(' if possible
            if open_count < n:
                # Build
                path.append("(")
                # Explore
                dfs_backtrack(open_count + 1, close_count, path)
                # Backtrack
                path.pop()
            
            # Process -> Choices : add ')' if it will not break validity
            if close_count < open_count:
                # Build
                path.append(")")
                # Explore
                dfs_backtrack(open_count, close_count + 1, path)
                # Backtrack
                path.pop()
        
        dfs_backtrack(0, 0, [])
        return res

    # Example: generateParenthesis(3) -> ["((()))","(()())","(())()","()(())","()()()"]

    def exist(board, word):
        rows, cols = len(board), len(board[0])
        
        def dfs_backtrack(r, c, idx):

            # Early exit:
            # Process Root -> : matched full word
            if idx == len(word):
                return True

            # Early Pruning -> : check boundaries
            if r < 0 or c < 0 or r >= rows or c >= cols:
                return False

            # Early Pruning -> : check current cell
            if board[r][c] != word[idx]:
                return False
            

            # Process -> Choices : explore all 4 directions

            # Build: mark current cell as exploring
            tmp, board[r][c] = board[r][c], "#"

            # Explore: recurse to neighbor cell
            found = (dfs_backtrack(r+1, c, idx+1) or
                     dfs_backtrack(r-1, c, idx+1) or
                     dfs_backtrack(r, c+1, idx+1) or
                     dfs_backtrack(r, c-1, idx+1))

            # Backtrack: Restore cell
            board[r][c] = tmp
            return found
        
        # dfs_backtrack starting from all cells
        for r in range(rows):
            for c in range(cols):
                if dfs_backtrack(r, c, 0):
                    return True

        return False

    # Example: exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCCED") -> True

    def solveNQueens(n):
        res = []
        cols = set()
        diag1 = set()  # r - c
        diag2 = set()  # r + c
        
        board = [["."] * n for _ in range(n)]
        
        def dfs_backtrack(r):
            # Process Root -> : all queens placed
            if r == n:
                res.append(["".join(row) for row in board])
                return
            
            # Process -> Choices : try each column
            for c in range(n):
                if c in cols or (r-c) in diag1 or (r+c) in diag2:
                    continue
                
                # Build: place queen
                board[r][c] = "Q"
                cols.add(c); diag1.add(r-c); diag2.add(r+c)
                
                # Explore: recurse to next row
                dfs_backtrack(r + 1)
                
                # Backtrack: remove queen
                board[r][c] = "."
                cols.remove(c); diag1.remove(r-c); diag2.remove(r+c)
        
        dfs_backtrack(0)
        return res

    # Example: solveNQueens(4) -> [
    #   [".Q..","...Q","Q...","..Q."],
    #   ["..Q.","Q...","...Q",".Q.."]
    # ]    
    

    def partition(s):
        res = []

        def is_palindrome(sub):
            return sub == sub[::-1]
        
        def dfs_backtrack(start, path):
            # Process Root -> : reached end of string
            if start == len(s):
                res.append(path[:])
                return
            
            # Process -> Choices : try all possible substrings
            for end in range(start+1, len(s)+1):

                # Constraint check: palindrome check
                if is_palindrome(s[start:end]):

                    # Build: add substring
                    path.append(s[start:end])

                    # Explore: recurse to next string
                    dfs_backtrack(end, path)

                    # Backtrack: remove substring
                    path.pop()
        
        dfs_backtrack(0, [])
        return res

    # Example: partition("aab") -> [["a","a","b"], ["aa","b"]]

    def subsets(self, nums: List[int]) -> List[List[int]]:

        # Result list
        res = []
        path = []  # mutable path list defined once

        def dfs_backtrack(start: int):
            # Process Root -> shallow copy of current path (current subset)
            res.append(path[:])

            # Explore Choices -> for remaining elements
            for i in range(start, len(nums)):
                # Build: append current element
                path.append(nums[i])

                # Explore: recurse with next index
                dfs_backtrack(i + 1)

                # Backtrack: remove last element
                path.pop()

        dfs_backtrack(0)  # initial call, no path passed
        return res

    def subsets(self, nums: List[int]) -> List[List[int]]:

        # Note:
        # Iterative: Build subsets in order to append to existing subsets
        # 1. Process Root -> start with empty subset
        # 2. Process Choices -> for each num in nums, add to existing subsets
        # Result: Subsets continue building with new nums to provide all subsets

        # Process Root -> : start with empty subset
        res = [[]]

        # Process -> Choices : iterate through all numbers in nums
        # since we build as we go, we cant build backwards, so we cant create a duplicate?
        for n in nums:

            # Explore -> : iterate over existing subsets, append to create new subset
            for i in range(len(res)):

                # Build -> : for all existing subset, add curr number
                # new string 
                new = res[i] + [n]

                # Incorrect:
                # new = res[i].append(n)
                # .append() always returns None,
                # as modification is in-place

                # Explore -> : append new subset to allow for iterative exploration
                res.append(new)

                # Backtrack -> : implicit, existing subsets remain for following iterations

        # overall: time complexity
        # overall space complexity
        return res

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        
        # Note:
        # Recursive DFS backtracking: Track current path and sum
        # 1. Process Root -> check if current sum equals target
        # 2. Process Choices -> explore each candidate from current index onwards
        # 3. Backtrack -> remove last choice to try next candidate
        # Result: all valid combinations appended to res
        
        # Note:
        # "Late Pruning": pruning happens after adding elements. 
        # Branches grow first, then are cut off if sum exceeds target. 
        # Creates unnecessary branches compared to early pruning.

        res = []
        path = []

        def dfs_backtrack(start, currSum):

            # Process Root -> check if sum reached target, shallow copy
            if currSum == target:
                res.append(path[:])
                return

            # Late Branch Pruning -> we can only prune branch after adding elements
            if currSum > target:
                return

            # Process -> Choices : try each candidate from current index onward, prune when in branch
            for i in range(start, len(candidates)):

                # Build: Include candidates[i] to make a new path
                path.append(candidates[i])

                # Explore: recurse with new path with same i (allow reuse)
                dfs_backtrack(i, currSum + candidates[i])

                # Backtrack: remove last candidate, attempt curr path with next candidate
                path.pop()

        dfs_backtrack(0, 0)

        # overall: time complexity
        # overall: space complexity
        return res

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        
        # Note:
        # Sort candidates for early pruning
        # 1. Process Root -> check if remaining sum equals zero
        # 2. Process Choices -> try candidates <= remaining
        # 3. Backtrack -> remove last choice after recursion
        # Result: all valid combinations appended to res
        
        # "Early Pruning": we can skip adding candidates that exceed 
        # the remaining sum, pruning branches from the root itself. 
        # Avoids creating unnecessary branches

        res = []
        path = []

        # Sort ascending so pruning works
        candidates.sort()

        def dfs_backtrack(start, remaining):

            # Process Root -> check if sum reached target, shallow copy
            if remaining == 0:
                res.append(path[:])
                return

            # Process -> Choices : prune invalid candidates
            for i in range(start, len(candidates)):

                # grab candidate
                candidate = candidates[i]

                # Early Candidate Pruning -> : skip early if candidate exceeds remaining,
                if candidate > remaining:
                    break

                # Build: include candidate in path
                path.append(candidate)

                # Explore: recurse with same index (allow reuse)
                dfs_backtrack(i, remaining - candidate)

                # Backtrack: remove last element for next iteration
                path.pop()

        dfs_backtrack(0, target) 
        return res

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
                
        # Note:
        # Sort candidates ascending for effective early pruning
        # Recursive DFS backwards: Track global path and remaining sum
        # 1. Process Root -> check if remaining sum equals zero
        # 2. Early Pruning -> skip "include" branch if candidate > remaining sum
        # 3. Process Choices -> try each candidate from current index backwards
        # 4. Backtrack -> remove last choice after recursion
        # Result: all valid combinations appended to res
        
        # "Early Pruning" +  "Backward DFS": largest candidates are considered first,
        # branches exceeding target are skipped immediately, 
        # allows unnecessary branches than forward early pruning.

        res = []
        path = []

        # Sort ascending so pruning works (largest candidates explored first)
        candidates.sort()

        def dfs_backtrack(i, remaining):

            # Process Root -> : check if remaining sum equals zero, shallow copy
            if remaining == 0:
                res.append(path[:])
                return

            # For Loop Exit: no more candidates
            if i < 0:
                return

            # grab candidate
            candidate = candidates[i]

            # Early Candidate Pruning -> if candidate too large, skip
            if candidate > remaining:
                dfs_backtrack(i - 1, remaining)
                return

            # Build: add candidate into path
            path.append(candidate)

            # Explore: recurse with same index (reuse allowed), update remaining
            dfs_backtrack(i, remaining - candidate)

            # Backtrack: remove last included candidate
            path.pop()

            # For Loop Iteration: next candidate
            dfs_backtrack(i - 1, remaining)

        # recursion from last index
        dfs_backtrack(len(candidates) - 1, remaining)

        # overall: time complexity
        # overall: space complexity
        return res

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
                
        # Note:
        # Iterative DFS using explicit stack to simulate recursion
        # 1. Process Root -> push initial state
        # 2. Process Choices -> expand from current index forward
        # 3. Build -> include candidate into new path
        # 4. Explore -> push new state with reduced remaining sum
        # 5. Backtrack -> implicit when stack pops, no in-place undo needed
        # Result: collect all valid paths where remaining == 0

        res = []

        # Sort candidates ascending for pruning
        candidates.sort()

        # tuples (start, path, remaining)
        stack = [(0, [], target)]

        # Iterative DFS expansion
        while stack:

            # Pop last state (DFS order FIFO)
            (start, path, remaining) = stack.pop()

            # Process Root -> if remaining == 0, valid combination found
            if remaining == 0:
                res.append(path)
                continue

            # Process Choices -> try each candidate from current index forward
            for i in range(start, len(candidates)):

                # grab candidate
                candidate = candidates[i]

                # Early Candidate Pruning -> skip if candidate exceeds remaining
                if candidate > remaining:
                    break

                # Build -> include candidate into path (need new path obj, order not guaranteed in iterative)
                new_path = path + [candidate]

                # Explore -> push new state, allow reuse of same candidate i
                stack.append((i, new_path, remaining - candidate))

                # Backtrack -> implicit, no need to pop since previous path objs still exit


        # overall: time complexity
        # overall: space complexity
        return res

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        
        # Note:
        # Sort candidates ascending to align duplicates for pruning
        # Recursive DFS backtracking: Track current path and remaining sum
        # 1. Process Root -> check if remaining == 0 to record valid combination
        # 2. Process Choices -> explore each candidate from current index onward
        # 3. Early Pruning -> skip candidates larger than remaining sum
        # 4. Duplicate Pruning -> skip candidates equal to previous at same level
        # 5. Backtrack -> remove last choice to try next candidate
        # Result: all valid combinations appended to res

        res = []
        path = []

        # Sort for duplicate and early candidate pruning
        candidates.sort() 

        def dfs_backtrack(start: int, remaining: int):

            # Process Root -> : check if valid combination, shallow copy
            if remaining == 0:
                res.append(path[:])
                return
            
            # Process Choices -> : explore numbers from current index onward
            for i in range(start, len(candidates)):
                
                # Duplicate Pruning -> : matching values only allowed when i == start,
                # ex: candidates = [1, 1, 1, 2, 3], target = 3
                #
                # Root call: dfs(start=0, remain=3, path=[])
                # i = 0 -> 1 recurse dfs(start=1, remain=2, path=[1])
                # i = 1 -> 1 skipped (i > start and dup of i=0)
                # i = 2 -> 1 skipped (dup of i=1)
                # i = 3 -> 2 recurse dfs(start=4, remain = 1, path=[2])
                # i = 4 -> 3 recurse dfs(start=5, remain = 0, path=[3])
                
                # Forward rule: 'allow the first copy in a group, i == start'
                if i > start and candidates[i] == candidates[i - 1]:
                    continue

                # Early Pruning -> : candidate exceeds remaining sum
                if candidates[i] > remaining:
                    break

                # Build: include candidate[i]
                path.append(candidates[i])
                
                # Explore -> move to next index (cannot reuse same element)
                dfs_backtrack(i + 1, remaining - candidates[i])

                # Backtrack -> remove last included candidate
                path.pop()

        dfs_backtrack(0, target)

        # overall: time complexity
        # overall: space complexity 
        return res

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        
        # Note:
        # Sort ascending for duplicates and pruning
        # Recursive DFS backwards: Track path and remaining sum
        # 1. Process Root -> check if remaining == 0 to record valid combination
        # 2. Process Choices -> explore each candidate from current index backwards
        # 3. Early Pruning -> skip candidates larger than remaining
        # 4. Duplicate Pruning -> skip duplicates at same decision level
        # 5. Backtrack -> remove last choice after recursion
        # Result: all valid combinations appended to res

        res = []
        path = []

        candidates.sort()

        def dfs_backtracking(i, remaining):

            # Process Root -> remaining sum zero
            if remaining == 0:
                res.append(path[:])
                return

            # No more candidates
            if i < 0:
                return

            # Early Pruning -> candidate too large
            if candidates[i] > remaining:
                dfs_backtracking(i - 1, remaining)
                return

            # Duplicate Pruning -> : matching values only allowed when i == len(candidates)-1,
            # ex: candidates = [1, 1, 1, 2, 3], target = 3
            #
            # Root call: dfs(i=4, remain=3, path=[])
            # i = 4 -> 3 recurse dfs(i=3, remain=0, path=[3])
            # i = 3 -> 2 recurse dfs(i=2, remain=1, path=[2])
            # i = 2 -> 1 recurse dfs(i=1, remain=0, path=[1])
            # i = 1 -> 1 skipped (i < len-1 and dup of i=2)
            # i = 0 -> 1 skipped (i < len-1 and dup of i=1)

            # Backwards rule: 'allow the last copy in a group, i == len(candidates)-1'
            if i < len(candidates) - 1 and candidates[i] == candidates[i + 1]:
                dfs_backtracking(i - 1, remaining)
                return

            # Build -> include candidate[i]
            path.append(candidates[i])

            # Explore -> move backward without reusing same element
            dfs_backtracking(i - 1, remaining - candidates[i])

            # Backtrack -> remove last
            path.pop()

            # Explore -> skip candidate[i], move to next smaller index
            dfs_backtracking(i - 1, remaining)

        # Start recursion from last index
        dfs_backtracking(len(candidates) - 1, target)
        return res

    def permute(self, nums: List[int]) -> List[List[int]]:

        # Note:
        # Recursive DFS backtracking: Track current permutation path
        # 1. Process Root -> : check if path length == n to record full permutation
        # 2. Process Choices -> : grab remaining unused elements
        # 3. Early Pruning -> skip used elements
        # 4. Backtrack -> remove last choice from path and mark as unused
        # Result: all valid permutations appended to res

        res = []
        path = []

        # Track elements in the current path
        used = [False] * len(nums) 

        def backtrack():

            # Process Root -> : check if valid permutation
            if len(path) == len(nums):
                res.append(path[:])
                return
            
            # Process -> Choices : grab remaining unused number
            for i in range(n):
                
                # Early Candidate Pruning -> : skip used elements
                if used[i]:          
                    continue
                
                # Build -> : add nums[i] to path and used tracker
                path.append(nums[i])
                used[i] = True

                # Explore: recurse new path
                backtrack()

                # Backtrack: remove last choice
                path.pop()
                used[i] = False

        backtrack()

        # overall: time complexity
        # overall: space complexity
        return res

    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:

        # Note:
        # Recursive DFS backtracking: Track current subset path
        # 1. Process Root -> : record current subset path
        # 2. Process Choices -> : iterate elements from current index onward
        # 3. Prune Duplicates -> skip duplicates at same recursion level
        # 4. Backtrack -> remove last element before next choice
        # Result: all unique subsets appended to res 

        res = []
        path = []

        # Sort to bring duplicates together
        nums.sort()

        def backtrack(start):

            # Process Root -> : record current subset
            res.append(path[:])

            # Process -> Choices : explore elements from current index onward
            for i in range(start, len(nums)):

                # Early Candidate Pruning -> : skip duplicates
                if i > start and nums[i] == nums[i-1]:
                    continue
                
                # Build -> : include nums[i] in path
                path.append(nums[i])

                # Explore -> : recurse to next index
                backtrack(i + 1)

                # Backtrack -> : remove last element before trying next choice
                path.pop()

        backtrack(0)

        # overall: time complexity
        # overall: space complexity
        return res

    def exist(self, board: List[List[str]], word: str) -> bool:
        
        # Note:
        # Recursive DFS backtracking: Track current path matching word
        # 1. Process Root : check if current path matches word
        # 2. Process Choices -> : explore all 4 directions from current cell
        # 3. Prune -> : skip cells out of bounds, mismatched letters, or previously visited
        # 4. Backtrack -> : restore cell after recursion
        # Result: return True if any path matches the word

        rows, cols = len(board), len(board[0])
        
        def backtrack(r, c, i):

            # Process Root -> : full word matched
            if i == len(word):
                return True
            
            # Early Candidate Prune -> : out of bounds
            if r < 0 or c < 0 or r >= rows or c >= cols:
                return False

            # Early Candidate Prune -> : letter mismatch
            if board[r][c] != word[i]:
                return False
            
            # Build -> : mark current cell as visited
            tmp, board[r][c] = board[r][c], "#"
            
            # Explore -> : recurse in all 4 directions
            found = (backtrack(r+1, c, i+1) or
                     backtrack(r-1, c, i+1) or
                     backtrack(r, c+1, i+1) or
                     backtrack(r, c-1, i+1))
            
            # Backtrack -> : restore cell as unvisited
            board[r][c] = tmp
            return found

        # Try starting DFS from each cell
        for r in range(rows):
            for c in range(cols):
                if backtrack(r, c, 0):
                    return True
        return False

    def exist(self, board: List[List[str]], word: str) -> bool:
        
        # Note:
        # Recursive DFS backtracking with search pruning:
        # 1. Count letters on board and work to prune impossible searches
        # 2. Reverse word if last letter is rarer than first
        # 3. Process Root -> : check if current path matches word
        # 4. Process Choices -> : explore all 4 directions
        # 5. Prune -> : skip out of bounds, mismatched letters, previously visited
        # 6. Backtrack -> : restore board cell after recursion
        # Result: return True if any valid path matches word

        rows, cols = len(board), len(board[0])
        word_count = Counter(word)
        
        # counter for optimization
        board_count = Counter(c for row in board for c in row)
        
        # Early Word Prune -> : board doesn't contain enough letters for word
        for char, count in word_count.items():
            if board_count[char] < count:
                return False
        
        # Early Recurse Optimization -> : reverse word if last letter rarer than first
        if board_count[word[0]] > board_count[word[-1]]:
            word = word[::-1]
        
        def backtrack(r, c, i):

            # Process Root -> : reached end of word
            if i == len(word):
                return True
            
            # Early Candidate Prune -> : out of bounds
            if r < 0 or c < 0 or r >= rows or c >= cols:
                return False

            # Early Candidate Prune : letter mismatch
            if board[r][c] != word[i]:
                return False
            
            # Build -> : mark cell as visited
            tmp, board[r][c] = board[r][c], "#"

            # Explore -> : recurse in 4 directions
            found = (backtrack(r+1, c, i+1) or
                     backtrack(r-1, c, i+1) or
                     backtrack(r, c+1, i+1) or
                     backtrack(r, c-1, i+1))

            # Backtrack -> : restore cell
            board[r][c] = tmp
            return found
        
        # Process -> Choices : start DFS only from cells matching first letter
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == word[0]:
                    if backtrack(r, c, 0):
                        return True


        return False

    def partition(self, s: str) -> List[List[str]]:

        # Note:
        # Recursive DFS backtracking: Track current partition path
        # 1. Process Root -> : check if end of string reached, record valid partition
        # 2. Process Choices -> : try all substrings starting from current index
        # 3. Prune -> : skip substring if not palindrome
        # 4. Backtrack -> : remove last substring before next choice
        # Result: all possible palindrome partitions appended to res

        res = []
        path = []

        # Check if s[l:r+1] substring is a palindrome
        def is_palindrome(l, r) -> bool:
            while l < r:
                if s[l] != s[r]:
                    return False
                l += 1
                r -= 1
            return True

        def backtrack(start):

            # Process Root -> : reached end of string, valid partition
            if start == len(s):
                res.append(path[:])
                return

            # Process -> Choices : try all substrings starting from current index
            for end in range(start, len(s)):

                # Prune -> : skip if substring is not palindrome
                if is_palindrome(start, end):

                    # Build -> : add palindromic substring
                    path.append(s[start:end+1])

                    # Explore -> : recurse to next starting index
                    backtrack(end+1)

                    # Backtrack -> : remove last substring and try next partition
                    path.pop()

        backtrack(0)

        # overall: time complexity
        # overall: space complexity
        return res

    def partition(self, s: str) -> List[List[str]]:

        # Note:
        # Recursive DFS backtracking with precomputed palindrome table:
        # 1. Precompute palindromes in O(n^2) to avoid repeated checks
        # 2. Process Root -> : check if end of string reached
        # 3. Process Choices -> : explore all substring end positions
        # 4. Prune -> : skip substrings that are not palindromes
        # 5. Backtrack -> : remove last substring before next choice
        # Result: all palindrome partitions appended to res

        n = len(s)
        res = []
        path = []

        # Palindrome Table:  palindromes: True if s[i:j+1] is palindrome, False if
        is_pal = [[False]*n for _ in range(n)]

        # backwards -> forwards:
        # To compute is_pal[0][4], we need is_pal[1][3].
        # Since we loop i backwards, by the time we get to i = 0, 
        # the row i = 1 (all substrings starting at index 1) is already 
        # filled in.

        # iterate backwards
        for i in range(n-1, -1, -1):
            # iterate forward 
            for j in range(i, n):

                # substring length:
                # j - i + 1 <= 3 : if substring length is <= 3
                # ex: "a", "aa", "aba"

                # inner substrings:
                # is_pal[i+1][j-1] : relying on inner substrings
                # If the inside s[i+1:j] is a palindrome, and the outer chars match, then s[i:j+1] is also a palindrome.
                if s[i] == s[j] and ((j - i + 1) <= 3 or is_pal[i+1][j-1]):
                    is_pal[i][j] = True

        def backtrack(start):
            
            # Process Root -> : reached end of string
            if start == n:
                res.append(path[:])
                return

            # Process -> Choices : explore all substring end positions
            for end in range(start, n):

                # Prune -> : skip if not palindrome
                if is_pal[start][end]:

                    # Build -> : append substring
                    path.append(s[start:end+1])

                    # Explore -> : move to next index
                    backtrack(end+1)

                    # Backtrack -> : remove last substring
                    path.pop()

        backtrack(0)

        # overall: time complexity
        # overall: space complexity
        return res  

    def letterCombinations(self, digits: str) -> List[str]:
        
        # Note:
        # Recursive DFS backtracking: Track current letter path
        # 1. Process Root -> : path length equals digits length, record combination
        # 2. Process Choices -> : letters corresponding to current digit
        # 3. Build -> : append letter to path
        # 4. Explore -> : recurse to next digit
        # 5. Backtrack -> : remove last letter before trying next option
        # Result: all possible letter combinations appended to res

        # Empty check
        if not digits:
            return []

        # Map digits to letters
        digit_map = {
            "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
            "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
        }

        res = []
        path = []

        def backtrack(index):

            # Process Root -> : current path has full length
            if index == len(digits):
                res.append("".join(path))
                return
            
            # Process -> Choices : letters corresponding to current digit
            for char in digit_map[digits[index]]:

                # Build -> : choose current letter
                path.append(char)

                # Explore -> : move to next digit
                backtrack(index + 1)

                # Backtrack -> : remove last letter to try next option 
                path.pop()

        backtrack(0)

        # overall: time complexity
        # overall: space complexity
        return res

    def solveNQueens(self, n: int) -> List[List[str]]:

        # Note:
        # Recursive DFS backtracking: Track current row placement
        # 1. Process Root -> : all rows filled, record board configuration
        # 2. Process Choices -> : iterate columns in current row
        # 3. Prune -> : skip if column or diagonals threatened
        # 4. Build -> : place queen
        # 5. Explore -> : recurse to next row
        # 6. Backtrack -> : remove queen, free column/diagonals
        # Result: all valid board configurations appended to res

        res = []

        # n x n size board
        board = [["."] * n for _ in range(n)]
        
        # 3 Sets to track threatened positions:
        
        # Columns occupied
        cols = set()
        # Rows occupied
        # rows = set() <- inherently tracked by recursion, no need for this

        # r - c diagonals: all cells on this diagonal have same value of row - col
        diag1 = set()
        # r + c diagonals: all cells on this diagonal have same value of row + col
        diag2 = set()

        def dfs_backtrack(row: int):

            # Process Root -> : all queens placed successfully, append board
            if row == n:
                res.append(["".join(r) for r in board])
                return
            
            # Process -> Choices : columns in current row
            for col in range(n):

                # Prune -> : skip if column or diagonals threatened
                if col in cols or (row - col) in diag1 or (row + col) in diag2:
                    continue
                
                # Build -> : place queen at (row, col)
                board[row][col] = "Q"
                cols.add(col)
                diag1.add(row - col)
                diag2.add(row + col)
                
                # Explore -> : move to next row
                # due to (row+1), we will never have overlapping rows
                dfs_backtrack(row + 1)
                
                # Backtrack -> : remove queen and free column/diagonals
                board[row][col] = "."
                cols.remove(col)
                diag1.remove(row - col)
                diag2.remove(row + col)

        dfs_backtrack(0)

        # overall: time complexity
        # overall: space complexity
        return res

    def solveNQueens(self, n: int) -> List[List[str]]:

        # Note:
        # Recursive DFS with bitmasking: Track available columns/diagonals
        # 1. Process Root -> : all rows filled, convert path to board
        # 2. Process Choices -> : available positions using bitmask
        # 3. Build -> : pick rightmost available position
        # 4. Explore -> : recurse with updated masks and path
        # 5. Backtrack -> : implicit via new path list
        # Result: all valid board configurations appended to res

        res = []
        path = []

        def backtrack(row, cols, diag1, diag2):
            
            # Process Root -> : all queens placed successfully
            if row == n:
                board = []
                for r in path:
                    row_str = ["." for _ in range(n)]
                    row_str[r] = "Q"
                    board.append("".join(row_str))
                res.append(board)
                return
            
            # Process -> Choices : calculate available positions with bitmasking
            available = ((1 << n) - 1) & (~(cols | diag1 | diag2))
            
            while available:
                
                # Build -> : pick rightmost available position
                pos = available & -available
                available &= available - 1        # Remove chosen position
                col = (pos - 1).bit_length()
                
                path.append(col)

                # Explore -> : recurse to next row with updated masks
                backtrack(
                    row + 1,
                    cols | pos,
                    (diag1 | pos) << 1,
                    (diag2 | pos) >> 1
                )

                # Backtrack -> :  remove last
                path.pop()

        backtrack(0, 0, 0, 0)

        # overall: time complexity
        # overall: space complexity
        return res