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]]:

        # Backtracking:
        # DFS recursion builds the power set solution incrementally,
        # by exploring all possible choices at each step.

        # Choices:
        # At each step we can either include or exclude a number,
        # giving us 2 options, so we get 2^n 

        # Shallow Copy:
        # A shallow copy means that the top level object is copied, 
        # but the elements inside are not duplicated, 
        # and still reference the original object.
        # In python this is fine because integers are immutable
        # tc: copy in O(n), since path can have up to n elements
        # sc: copy in O(n), list of n elements added to the result list

        # Backtracking Recursion Stack Storage:
        # All subsets of n elements for 2^n subsets
        # sc: O(n * 2^n)
        res = []

        # Path Storage:
        # holds current subset path during recursion exploration, max length n
        # sc: O(n)
        path = []  

        def dfs(start: int):
            
            # 2 Paths determined by 2 choices:
            # include or exclude the current number

            # Path 1:
            # Include current number,
            # stop including any further integers from here on
            # tc: O(n)
            res.append(path[:])

            # Path 2:
            # Do not include current number.
            # DFS exploration will test the following next 2 choices
            # tc: O(n)
            for i in range(start, len(nums)):

                # Prepare To Explore:
                # (Will Become Path 1 on exploration)
                # Add integer to exploration path
                # and pass start index to ensure we only include new integers
                # tc: O(1)
                path.append(nums[i])

                # Recurse And Explore
                # tc: O(2^n)
                dfs(i+1)

                # Backtrack: 
                # Revert path 2 integer to try another integer via the for loop
                # tc: O(1)
                path.pop()

        # Start backtracking at "root"
        # tc: O(2^n)
        dfs(0)

        # overall: tc O(n * 2^n)
        # overall: sc O(n * 2^n)
        return res

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

        # Generator / Yield vs Result List:
        # Used to avoid storing/holding all subsets in memory at once

        # Yield:
        # Using 'yield', we generate subsets one at a time instead of storing them all.
        # The generator pauses at each 'yield' and resumes when the next subset is requested.
        # As a result, only the current path and recursion stack are kept in memory,
        # reducing auxiliary space to O(n), which is due to the size O(n) of any subset
        # but still independent by the total number of subsets.

        # Generator / Yield Auxiliary space (not counting the output):
        # Only the current subset path and recursion stack are in memory, 
        # O(n) instead of O(n * 2^n)

        # Path Storage:
        # holds current subset path during recursion exploration, max length n
        # sc: O(n)
        path = []


        def dfs(start):
            
            # 2 Paths determined by 2 choices:
            # include or exclude the current number

            # Process Root:
            # Yield the current subset (shallow copy of path)
            # tc: O(n) to copy path
            # sc: O(n) for copy, added to output by caller if collected
            yield path[:]

            # Explore All Choices:
            # Iterate over remaining elements starting from index `start`
            # tc: O(n) per level, total recursive calls = 2^n
            for i in range(start, len(nums)):

                # Build New Path:
                # Append current number to path
                # tc: O(1), sc: O(1)
                path.append(nums[i])


                yield from dfs(i + 1)

                # Backtrack To Current Path:
                # Remove last number to explore alternative paths
                # tc: O(1), sc: O(1)
                path.pop()

        # Generator:
        # We create a generator which is passed back to the caller.
        # At this moment we have not found and stored any of the subsets
        # tc: O(1) to create generator
        # sc: O(1) auxiliary for the generator object itself
        generator = dfs(0)

        # Consuming:
        # To get subsets, we need to consume the generator,
        # either by Streaming or Storing In Memory

        # 1. Streaming: iterate over res directly
        #   for subset in res:
        #         print(subset)        ->   subsets will be generated one by one
        
        # 2. Storing In Memory: convert res to a list to store all subsets in memory:
        #   allSubsets = list(res)    ->   now all subsets are generated and stored

        # Note:
        # Choice 2 ignores the issue we were trying to solve of storing everything in memory at one time,
        # Choice 1 would be better as at any moment we are only storing/printing O(1) subset

        # Here we are forced to use Choice 2 because LeetCode's auto-grader inspects 
        # our function to return a value of type List[List[int]]
        res = list(generator)

        # overall: tc O(n * 2^n)    # must generate all subsets, each copied
        # overall: sc O(n)          # only care about size of single subset, allowed by generator
        # overall: sc O(n * 2^n)    # saving size of single subset per each subset, after consuming generator
        return res

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

        # Backtracking:
        # Recursive function will build subsets incrementally,
        # by using DFS to explore all possible choices at each step.

        # Duplicate Pruning:
        # Sorting brings equal values next to each other, so within a single
        # level of the recursion we only take the first occurrence of a
        # duplicate value and skip the rest -- this avoids generating the same
        # subset more than once (the same value is still reachable deeper in
        # the recursion, just not as a second choice at the same level).

        # sc: O(n * 2^n) 2^n subsets each length up to n
        res = []

        # sc: O(n), holds current subset during recursion of max length n
        path = []

        # Sort ascending to bring duplicates together
        nums.sort()

        def dfs(start):

            # New Valid subset:
            # add to final res

            # Path 1:
            # record current subset, valid at every node not just leaves
            # tc: O(n) subset max length n
            res.append(path[:])

            # Path 2:
            # try including any element we have not added yet,
            # ignoring those we have included via start index
            # tc: O(n)
            for i in range(start, len(nums)):

                # Duplicate Pruning:
                # only allow the first copy in a group of equal values at this level,
                # i == start is always allowed since there's nothing valid to compare yet
                if i > start and nums[i] == nums[i - 1]:
                    continue

                # Add element to testing subset
                path.append(nums[i])

                # Explore:
                # explore this subset and move to next index to avoid reusing current element
                # tc: O(2^n) total recursive calls (all possible subsets)
                dfs(i + 1)

                # Backtrack:
                # Revert adding element to try another element via the for loop
                path.pop()

        # Start backtracking at "root"
        dfs(0)

        # overall: tc O(n * 2^n)
        # overall: sc O(n * 2^n)
        return res

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

        # Backtracking:
        # Recursive function will explore every subset incrementally,
        # by using DFS to explore all possible choices at each step,
        # the same traversal shape as generating all subsets (LC 78),
        # except instead of storing each subset we accumulate its XOR total.

        # At each step we can either include or exclude a number,
        # giving us 2 options, so we get 2^n subsets total.

        # sc: O(n), holds current path during recursion of max length n
        path = []

        # sc: O(1), running sum of every subset's XOR total
        self.total = 0

        # tc: O(n * 2^n)  2^n subsets, each XOR computed and summed
        # sc: O(n)        recursion stack + path, no result list needed
        def dfs(start: int, curXor: int):

            # New Valid subset:
            # add its XOR total to the running sum

            # Path 1:
            # stop including any further integers from here on, so no need to keep exploring
            # tc: O(1)
            self.total += curXor

            # Path 2:
            # try including any integer we have not added yet,
            # ignoring those we have included via start index
            # tc: O(n)
            for i in range(start, len(nums)):

                # Add integer to testing subset
                path.append(nums[i])

                # Explore:
                # explore this subset, XOR the new number into curXor,
                # and pass start index for including new integers
                # tc: O(2^n)
                dfs(i + 1, curXor ^ nums[i])

                # Backtrack:
                # Revert adding integer to try another integer via the for loop
                path.pop()

        # Start backtracking at "root" with an empty subset (XOR total 0)
        dfs(0, 0)

        # overall: tc O(n * 2^n)
        # overall: sc O(n)
        return self.total

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

        # Bit Manipulation:
        # Instead of enumerating all 2^n subsets, we reason about each bit
        # position independently: for a fixed bit position, how many of the
        # 2^n subsets have that bit set in their XOR total?

        # Key Insight:
        # A given bit position ends up set in a subset's XOR total only if an
        # ODD number of elements in that subset have that bit set. If at least
        # one number in nums has a bit set, then across all 2^n subsets,
        # exactly half (2^(n-1)) of them contain an odd count of that bit --
        # this holds because for every subset with an odd count, pairing it
        # with/without any one fixed "bit-set" element flips it to an even
        # count and back, giving a perfect 1:1 split between odd and even.
        # If NO number has that bit set, 0 subsets contribute it, obviously.

        # Reduction:
        # So a bit contributes to the final sum only if it's set in at least
        # one number (captured by OR-ing every number together), and when it
        # does contribute, it contributes exactly 2^(n-1) times. This means
        # the final answer is just: (OR of all nums) * 2^(n-1), which is the
        # same as left-shifting the OR result by (n - 1) bits.

        # sc: O(1), single accumulator
        orTotal = 0

        # tc: O(n), OR every number together
        for num in nums:

            # Combine:
            # OR in this number's bits, any bit set here is set in at least
            # one subset element and will contribute to the final sum
            orTotal |= num

        # overall: tc O(n)
        # overall: sc O(1)
        return orTotal << (len(nums) - 1)

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        
        # Backtracking:
        # Recursive function will build valid combinations incrementally,
        # by using DFS to explore only choices that can still reach the target.

       # Early Pruning:
        # Sorting candidates ascending lets us skip candidates that exceed the
        # remaining sum before ever recursing into them, pruning branches from
        # the root itself instead of recursing first and discovering they're invalid.

        # sc: O(n)
        res = []

        # sc: O(depth), holds current subset during recursion
        path = []

        # Sort ascending to allow early pruning
        candidates.sort()

        def dfs(start, remaining):

            # New Valid combination:
            # add to final res

            # Path 1:
            # remaining sum has hit zero, no further candidates needed
            # tc: O(depth) subset max length depth
            if remaining == 0:
                res.append(path[:])
                return

            # Path 2:
            # try including any candidate we have not added yet,
            # ignoring those we have skipped via start index
            # tc: O(n)
            for i in range(start, len(candidates)):

                candidate = candidates[i]

                # Early Pruning:
                # candidates are sorted ascending, 
                # so if this one exceeds remaining all others after it will too,
                # so we can stop exploring this branch entirely 
                if candidate > remaining:
                    break

                # Add candidate to testing subset
                path.append(candidate)

                # Explore:
                # explore this subset and pass same index to allow reuse of current candidate
                # tc: O(n^(target/min_cand))
                dfs(i, remaining - candidate)

                # Backtrack:
                # Revert adding candidate to try another candidate via the for loop
                path.pop()

        # Start backtracking at "root"
        dfs(0, target)

        # overall: tc O(n^(target/min_cand))
        # overall: sc O(target/min_cand + output size)
        return res

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
       
        # Backtracking:
        # Recursive function will build valid combinations incrementally,
        # by using DFS to explore only choices that can still reach the target.
        # Unlike combinationSum, each candidate can only be used once, and the
        # input may contain duplicate values that must not produce duplicate combinations.

        # Early Pruning:
        # Sorting candidates ascending lets us skip candidates that exceed the
        # remaining sum before ever recursing into them, pruning branches from
        # the root itself instead of recursing first and discovering they're invalid.

        # Duplicate Pruning:
        # Sorting also aligns equal values next to each other, so within a single
        # level of the recursion we only take the first occurrence of a duplicate
        # value and skip the rest -- this avoids generating the same combination
        # more than once (a later, later-occurring duplicate is still reachable
        # deeper in the recursion, just not as a second choice at the same level)

        # sc: O(depth)
        res = []
        
        # sc: O(depth), holds current subset during recursion
        path = []

        # Sort ascending to allow early pruning and duplicate pruning
        candidates.sort() 

        def dfs(start, remaining):

            # 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:
                # Only use the first copy of an integer, check if previous index is a duplicate.
                # i > start ensures the first iteration is always valid,
                # only candidates after the first iteration get compared for avoiding negative indexing
                if i > start and candidates[i] == candidates[i - 1]:
                    continue

                # Early Pruning:
                # candidates are sorted ascending, so if this one exceeds remaining
                # all others after it will too, so we can stop exploring this branch entirely
                if candidates[i] > remaining:
                    break

                # Add candidate to testing subset
                path.append(candidates[i])

                # Explore:
                # explore this subset and move to next index, since each candidate
                # can only be used once (no reuse of current index, unlike combinationSum)
                # tc: O(2^n) in the worst case, fewer in practice due to pruning
                dfs(i + 1, remaining - candidates[i])

                # Backtrack:
                # Revert adding candidate to try another candidate via the for loop
                path.pop()

        # Start backtracking at "root"
        dfs(0, target)

        # overall: tc O(n * 2^n)
        # overall: sc O(n + output size)
        return res

    def combinationSum3(self, k: int, n: int) -> List[List[int]]:

        # Backtracking:
        # Recursive function will build valid combinations incrementally,
        # by using DFS to explore only choices that can still reach both the
        # target sum and the exact count k, same shape as Combination Sum
        # (LC 39), with two constraints tracked together instead of one.

        # Early Pruning:
        # Candidates 1-9 are naturally sorted ascending, so once a candidate
        # exceeds the remaining sum, every candidate after it will too --
        # prune that branch immediately instead of recursing into it.

        # Count Pruning:
        # Since each number is used at most once and only 1-9 are available,
        # we can also stop exploring a branch early if there aren't enough
        # remaining candidates left to reach k numbers, or if the path has
        # already reached k numbers without reaching n.

        # sc: O(k)
        res = []

        # sc: O(k), holds current path during recursion, max length k
        path = []

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

            # New Valid combination:
            # add to final res

            # Path 1:
            # path has exactly k numbers and remaining sum has hit zero
            # tc: O(k) subset max length k
            if len(path) == k and remaining == 0:
                res.append(path[:])
                return

            # Path 2:
            # path already has k numbers but sum hasn't hit zero, or no
            # candidates remain -- neither can lead to a valid combination
            if len(path) == k or start > 9:
                return

            # Path 3:
            # try including any candidate from 'start' through 9 we have not added yet
            # tc: O(9) per call, bounded by fixed digit range
            for candidate in range(start, 10):

                # Early Pruning:
                # candidates are ascending, so if this one exceeds remaining
                # all others after it will too, so we can stop exploring this branch entirely
                if candidate > remaining:
                    break

                # Add candidate to testing subset
                path.append(candidate)

                # Explore:
                # explore this subset and move to next digit, since each candidate
                # can only be used once (no reuse of current digit)
                # tc: O(C(9, k)) total combinations in the worst case, fewer with pruning
                dfs(candidate + 1, remaining - candidate)

                # Backtrack:
                # Revert adding candidate to try another candidate via the for loop
                path.pop()

        # Start backtracking at "root"
        dfs(1, n)

        # overall: tc O(C(9, k) * k)
        # overall: sc O(k)
        return res

    def generateParenthesis(self, n: int) -> List[str]:
        
        # Backtracking:
        # Recursive function will build valid parenthesis sequences incrementally,
        # by using DFS to explore only choices that keep the sequence valid so far.


        # List Mutability:
        # We use a single list 'curr' and modify it in place using append/pop.
        # The list only gets converted when we find a valid combination of length O(n)
        # There are Catalan(n) valid sequences each of length O(n)

        # sc: O(Catalan(n) * n), holds all valid sequences once complete
        res = []
        
        def dfs(current, openCount, closeCount):

            # New Valid sequence:
            # add to final res

            # Path 1:
            # both open and close counts have reached n, valid sequence found
            # tc: O(n) to join current into a string
            if openCount == n and closeCount == n:
                res.append("".join(current))
                return

            # Path 2a:
            # add an open paren, if don't have n total yet,
            # ensuring the sequence never has more '(' than allowed
            if openCount < n:

                # Choose:
                # append open '('
                current.append('(')

                # Explore:
                # recurse with updated counts
                dfs(current, openCount + 1, closeCount)

                # Backtrack:
                # remove last open '('
                current.pop()

            # Path 2b:
            # add a close paren, if we have less than the number of open paren,
            # ensuring every close paren has an open paren to pair with it
            if closeCount < openCount:

                # Choose:
                # append close ')'
                current.append(')')

                # Explore:
                # recurse with updated counts
                dfs(current, openCount, closeCount + 1)

                # Backtrack:
                # remove last close ')'
                current.pop()

        # Start backtracking at "root", empty list passed
        backtrack([], 0, 0)

        # overall: tc O(Catalan(n) * n)
        # overall: sc O(Catalan(n) * n)
        return res

    def generateParenthesis(self, n: int) -> List[str]:
        
        # Dynamic Programming:
        # We exploit the recursive structure of Catalan numbers
        # by building a list of all valid parentheses combinations for each level n

        # Two Pointer:
        # If we have a list of valid combinations of parenthesis, 
        # we can append them in a format that generate more valid combinations

        # dp:    list of list of parentheses combinations 
        # dp[n]: list containing all valid parenthesis combinations for the nth level (n pair of parenthesis)
        dp = []
        for _ in range(n + 1):
            dp.append([])     

        # Base case: valid combination for n = 0
        dp[0] = [""]  
        
        # Iterate: create valid lists from dp[1] to dp[n]
        # Current: building list for ith pair
        # tc: iterate over list of n length O(n) 
        for i in range(1, n + 1): 

            # iterate over stored lists up to now
            for j in range(i):  

                # Opposite Ends Two Pointer Variation:
                # Since pointers will meet in middle and cross each other, 
                # they will get all variations of combinations already built,
                # which allows us to format them to generate more valid combinations

                # Setup: Opposite Ends Two Pointer Variation
                # Forward and Reverse Iteration

                # Forward Iteration List 1: 
                # Iterate over each valid string of parentheses for level j,
                # starting at first parentheses pairs level of 0 pairs of parenthesis
                for left in dp[j]:

                    # Reverse Iteration List 2: 
                    # Iterate over each valid string of parentheses for level (i - 1 - j),
                    # starting at last parenthesis pairs level of largest number pairs currently available
                    for right in dp[i - 1 - j]:

                        # Generation Format:
                        # ({left}){right} or {left}({right}) are both valid formulas
                        # Since we are doing Opposite Ends and left and right will cross over each other,
                        # left and right will both individually use all values
                        # which means with these 2 iterations
                        # we are eventually doing both the same thing
                        # dp[i].append(f"{left}({right})")
                        dp[i].append(f"({left}){right}")

        # overall: tc O(Catalan(n) * n)
        # overall: sc O(Catalan(n) * n)
        return dp[n]

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

        # Backtracking:
        # Recursive function will build permutations incrementally,
        # by using DFS to explore every not-yet-used element at each position.

        # Element Usage Tracking:
        # Unlike subset/combination problems, order matters here and every
        # element must appear exactly once per permutation, so instead of a
        # start index we track which elements have already been placed in the
        # current path with a 'used' boolean array, and skip those.

        # sc: O(n)
        res = []

        # sc: O(n), holds current path during recursion, max length n
        path = []

        # sc: O(n), tracks which elements are already in the current path
        used = [False] * len(nums)

        def dfs():

            # New Valid permutation:
            # add to final res

            # Path 1:
            # path length has reached n, every element has been placed
            # tc: O(n) subset max length n
            if len(path) == len(nums):
                res.append(path[:])
                return

            # Path 2:
            # try including any element that has not been used yet
            # tc: O(n)
            for i in range(len(nums)):

                # Early Candidate Pruning:
                # skip elements already placed in the current path
                if used[i]:
                    continue

                # Add element to testing path
                path.append(nums[i])
                used[i] = True

                # Explore:
                # explore this path, all remaining unused elements are still candidates
                # tc: O(n!) total recursive calls (all possible permutations)
                dfs()

                # Backtrack:
                # Revert adding element to try another element via the for loop
                path.pop()
                used[i] = False

        # Start backtracking at "root"
        dfs()

        # overall: tc O(n * n!)
        # overall: sc O(n)
        return res

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

        # Backtracking:
        # Recursive function will build permutations incrementally,
        # by using DFS to explore every not-yet-used element at each position,
        # same traversal shape as Permutations (LC 46), extended to skip
        # duplicate values so no permutation is generated more than once.

        # Element Usage Tracking:
        # Order matters here and every element must appear exactly once per
        # permutation, so instead of a start index we track which elements
        # have already been placed in the current path with a 'used' boolean
        # array, and skip those.

        # Duplicate Pruning:
        # Sorting brings equal values next to each other. At each position in
        # the permutation (each level of recursion), we only allow the first
        # not-yet-used copy of a repeated value to be placed -- if an earlier
        # copy of the same value hasn't been used yet, placing a later copy
        # first would just produce a permutation identical to one we'll
        # already generate by placing the earlier copy first.

        # sc: O(n)
        res = []

        # sc: O(n), holds current path during recursion, max length n
        path = []

        # sc: O(n), tracks which elements are already in the current path
        used = [False] * len(nums)

        # Sort ascending so duplicates sit next to each other
        nums.sort()

        def dfs():

            # New Valid permutation:
            # add to final res

            # Path 1:
            # path length has reached n, every element has been placed
            # tc: O(n) subset max length n
            if len(path) == len(nums):
                res.append(path[:])
                return

            # Path 2:
            # try including any not-yet-used element
            # tc: O(n)
            for i in range(len(nums)):

                # Early Candidate Pruning:
                # skip elements already placed in the current path
                if used[i]:
                    continue

                # Duplicate Pruning:
                # skip a repeated value if the previous identical value hasn't
                # been used yet -- ensures duplicates are only ever placed in
                # left-to-right order at this level, avoiding duplicate permutations
                if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                    continue

                # Add element to testing path
                path.append(nums[i])
                used[i] = True

                # Explore:
                # explore this path, all remaining unused elements are still candidates
                # tc: O(n!) total recursive calls in the worst case, fewer with duplicates
                dfs()

                # Backtrack:
                # Revert adding element to try another element via the for loop
                path.pop()
                used[i] = False

        # Start backtracking at "root"
        dfs()

        # overall: tc O(n * n!)
        # overall: sc O(n)
        return res

    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:

        # Backtracking:
        # Recursive function will build paths from node 0 to node n-1
        # incrementally, by using DFS to extend the current path along every
        # outgoing edge. Since the graph is guaranteed to be a DAG, there are
        # no cycles to worry about, so no visited set is needed -- every path
        # DFS explores is guaranteed to terminate.

        # Adjacency List (as given):
        # graph = [
        #           [1, 2],     0 -> 1, 0 -> 2
        #           [3],        1 -> 3
        #           [3],        2 -> 3
        #           [],         3 has no outgoing edges
        #         ]
        # Unlike most graph problems, the input here is already an Adjacency
        # List -- graph[i] is literally the list of nodes reachable from i.
        # There's no Edge List to transform first.

        n = len(graph)

        # sc: O(2^V * V) worst case, DAG can have exponentially many paths
        res = []

        # sc: O(V), holds current path during recursion, max length V
        path = [0]

        def dfs(node):

            # New Valid path:
            # reached the target, record a copy of the current path
            # tc: O(V) to copy path
            if node == n - 1:
                res.append(path[:])
                return

            # Path 1:
            # try extending the path along every outgoing edge from this node
            for nei in graph[node]:

                # Choose:
                # extend path with neighbor
                path.append(nei)

                # Explore:
                # recursively explore neighbor
                dfs(nei)

                # Backtrack:
                # remove neighbor so sibling branches can reuse path
                path.pop()

        # Start backtracking at "root", node 0
        dfs(0)

        # overall: tc O(2^V * V), up to 2^V paths in the worst case DAG, each up to V nodes to copy
        # overall: sc O(2^V * V), for storing all paths in res
        #   (auxiliary space, excluding output, is O(V) for recursion stack + path)
        return res

    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:

        # Backtracking (Iterative):
        # Same idea as Solution 1 -- build paths from node 0 to node n-1 by
        # extending along every outgoing edge -- but explored via a queue
        # instead of recursion. Since BFS has no call stack to backtrack on,
        # each queue entry must carry its OWN independent copy of the path
        # so far -- there's no shared mutable list to undo after a node.

        # Unlike single-target BFS problems, we can't stop at the first time
        # the target is reached, since every path is needed, not just the
        # shortest one. Every time a path reaches the target it's recorded,
        # but BFS continues until the queue is empty so all other
        # in-progress paths are still explored.

        n = len(graph)

        # sc: O(2^V * V) worst case, DAG can have exponentially many paths
        res = []

        # sc: O(2^V * V), queue can hold many in-progress paths at once,
        # each up to O(V) long, with its own independent copy
        queue = deque([[0]])

        while queue:

            # Pop a path from the queue
            path = queue.popleft()

            # Grab the last node in this path to explore its neighbors
            node = path[-1]

            # New Valid path:
            # reached the target, record this complete path
            if node == n - 1:
                res.append(path)
                continue

            # Path 1:
            # try extending the path along every outgoing edge from this node
            for nei in graph[node]:

                # Choose + Explore:
                # build a new path with neighbor appended, queue for further exploration
                # tc: O(V) per enqueue to copy and extend path
                queue.append(path + [nei])

        # overall: tc O(2^V * V), up to 2^V paths in the worst case DAG, each up to V nodes to build/copy
        # overall: sc O(2^V * V), for storing all paths in the queue and res
        return res

    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:

        # Backtracking:
        # Recursive function will trace root-to-leaf paths incrementally,
        # by using DFS to descend into every subtree while tracking the
        # running path and remaining sum still needed. Unlike a problem
        # that can stop at the first valid path, every root-to-leaf path
        # must be explored, and any that sum to targetSum must be collected.

        # sc: O(n) worst case (skewed tree), holds all collected paths
        res = []

        # sc: O(h), holds current path during recursion, max length = tree height h
        path = []

        def dfs(node, remaining):

            # Path 1:
            # reached past a leaf, empty subtree cannot complete a path
            if not node:
                return

            # Choose:
            # add this node to the current path before descending
            path.append(node.val)
            remaining -= node.val

            # New Valid path:
            # true leaf -- no left AND no right child -- record this path
            # only if it exactly accounts for the remaining amount
            if not node.left and not node.right:
                if remaining == 0:
                    # tc: O(h) to copy path, since path keeps mutating
                    res.append(path[:])

            # Path 2:
            # a node with only one child is NOT a leaf, keep exploring
            # whichever sides exist
            else:

                # Explore:
                # recurse into left and right subtrees with updated remaining
                dfs(node.left, remaining)
                dfs(node.right, remaining)

            # Backtrack:
            # remove this node before returning to the parent call,
            # so it doesn't leak into sibling paths
            path.pop()

        # Start backtracking at "root"
        dfs(root, targetSum)

        # overall: tc O(n^2) worst case, n calls each doing O(n) path copy on a skewed tree
        # overall: sc O(n) worst case, recursion stack + path, skewed tree
        return res

    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:

        # Backtracking (Iterative):
        # Same "remaining sum" and "true leaf" rules as Solution 1, but
        # explored level by level via a queue instead of recursion. Since
        # BFS has no call stack to backtrack on, each queue entry must carry
        # its OWN independent copy of the path so far -- there's no shared
        # mutable list to undo after processing a node.

        # Path 1:
        # empty tree has no path at all
        if not root:
            return []

        # sc: O(n) worst case (skewed tree), holds all collected paths
        res = []

        # sc: O(n), holds (node, remaining, path) tuples currently queued,
        # each path copy up to O(h) long
        queue = deque([(root, targetSum - root.val, [root.val])])

        while queue:

            # Pop next node, its remaining amount, and its path so far
            node, remaining, path = queue.popleft()

            # New Valid path:
            # true leaf -- no left AND no right child -- record this path
            # only if it exactly accounts for the remaining amount
            if not node.left and not node.right:
                if remaining == 0:
                    res.append(path)
                continue

            # Choose + Explore:
            # enqueue children that exist, each with its own path copy
            # extended by that child's value -- a missing side simply
            # never gets enqueued
            # tc: O(h) per enqueue to copy and extend path
            if node.left:
                queue.append((node.left, remaining - node.left.val, path + [node.left.val]))
            if node.right:
                queue.append((node.right, remaining - node.right.val, path + [node.right.val]))

        # overall: tc O(n^2) worst case, each of n nodes does an O(n) path copy on a skewed tree
        # overall: sc O(n^2) worst case, every queued path independently copies up to O(n) values
        return res

    def exist(self, board: List[List[str]], word: str) -> bool:

        # Backtracking:
        # Recursive function will trace a path through the grid incrementally,
        # by using DFS to try extending the current path in all 4 directions,
        # only continuing a branch while it still matches the word so far.

        # sc: O(1), rows/cols are fixed reference values, not per-cell storage
        rows, cols = len(board), len(board[0])

        def dfs(r, c, i):

            # Path 1:
            # every character in word has been matched, full path found
            if i == len(word):
                return True

            # Path 2:
            # cell is outside the grid, this direction can't be explored
            if r < 0 or c < 0 or r >= rows or c >= cols:
                return False

            # Path 3:
            # current cell doesn't match the next expected letter
            if board[r][c] != word[i]:
                return False

            # Choose:
            # mark current cell as visited by overwriting it, so the same
            # cell can't be reused later in this same path
            tmp, board[r][c] = board[r][c], "#"

            # Explore:
            # recurse in all 4 directions, short-circuit on first match found
            # tc: O(4^L) total recursive calls in the worst case, L = len(word)
            found = (dfs(r + 1, c, i + 1) or
                     dfs(r - 1, c, i + 1) or
                     dfs(r, c + 1, i + 1) or
                     dfs(r, c - 1, i + 1))

            # Backtrack:
            # restore original cell value so other starting points can reuse it
            board[r][c] = tmp
            return found

        # Try starting DFS from every cell on the board
        # tc: O(rows * cols) starting points
        for r in range(rows):
            for c in range(cols):
                if dfs(r, c, 0):
                    return True

        return False

        # overall: tc O(rows * cols * 4^L), L = len(word)
        # overall: sc O(L), recursion stack depth bounded by word length

    def exist(self, board: List[List[str]], word: str) -> bool:

        # Backtracking:
        # Same traversal shape as Solution 1 -- trace a path through the grid
        # via DFS in all 4 directions, only continuing while the path still
        # matches the word so far.

        # Optimization vs Solution 1:
        # Before searching, we can rule out impossible cases and cut down the
        # branching factor of the search:
        #   1. If the board doesn't contain enough of any letter the word
        #      needs, no path can possibly exist -- return False immediately.
        #   2. Starting the search from the rarer of the word's first/last
        #      letter reduces how many cells trigger a full DFS attempt, and
        #      tends to fail faster when there's no valid path, since rarer
        #      starting letters mean fewer branches explored overall.

        # sc: O(1), rows/cols are fixed reference values, not per-cell storage
        rows, cols = len(board), len(board[0])

        # sc: O(1), fixed alphabet size (26 letters) regardless of input size
        word_count = Counter(word)
        board_count = Counter(c for row in board for c in row)

        # Early Word Pruning:
        # if the board doesn't contain enough of any needed letter,
        # no path can possibly spell out the word
        # tc: O(len(word)) to check every distinct letter needed
        for char, count in word_count.items():
            if board_count[char] < count:
                return False

        # Early Recurse Optimization:
        # search from whichever end of the word is rarer on the board,
        # since starting from a rarer letter triggers fewer DFS attempts overall
        if board_count[word[0]] > board_count[word[-1]]:
            word = word[::-1]

        def dfs(r, c, i):

            # Path 1:
            # every character in word has been matched, full path found
            if i == len(word):
                return True

            # Path 2:
            # cell is outside the grid, this direction can't be explored
            if r < 0 or c < 0 or r >= rows or c >= cols:
                return False

            # Path 3:
            # current cell doesn't match the next expected letter
            if board[r][c] != word[i]:
                return False

            # Choose:
            # mark current cell as visited by overwriting it, so the same
            # cell can't be reused later in this same path
            tmp, board[r][c] = board[r][c], "#"

            # Explore:
            # recurse in all 4 directions, short-circuit on first match found
            # tc: O(4^L) total recursive calls in the worst case, L = len(word)
            found = (dfs(r + 1, c, i + 1) or
                     dfs(r - 1, c, i + 1) or
                     dfs(r, c + 1, i + 1) or
                     dfs(r, c - 1, i + 1))

            # Backtrack:
            # restore original cell value so other starting points can reuse it
            board[r][c] = tmp
            return found

        # Process Choices:
        # only start DFS from cells that match the (possibly reversed) first letter,
        # instead of every cell on the board like Solution 1
        # tc: O(rows * cols) worst case, fewer attempts in practice
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == word[0]:
                    if dfs(r, c, 0):
                        return True

        return False

        # overall: tc O(rows * cols * 4^L), L = len(word), same bound as Solution 1
        # overall: sc O(L), recursion stack depth bounded by word length

class TrieNode:

    def __init__(self):
        # sc: O(1) per node, grows to O(sum of word lengths) across whole Trie
        # dict of char subtrees for current node: char -> TrieNode
        self.subtrees = {}
        # marks whether this node is the end of a valid word
        self.isWord = False

    def addWord(self, word):

        # updated current node
        node = self

        # tc: O(len(word))
        for c in word:

            # if subtree does not exist, create
            if c not in node.subtrees:
                node.subtrees[c] = TrieNode()

            # iterate to subtree
            node = node.subtrees[c]

        # set as valid end of word
        node.isWord = True


class Solution:

    def findWords(self, board, words):

        # Backtracking + Trie:
        # Recursive function will explore every path on the board incrementally,
        # by using DFS to extend the current path only while it still matches
        # a valid prefix in the Trie built from 'words'. The Trie lets us check
        # "is this still a valid prefix" in O(1) per character instead of
        # comparing against every word individually.

        # sc: O(sum of len(word) for word in words), Trie holds every word's characters
        root = TrieNode()
        for word in words:
            root.addWord(word)

        # sc: O(1), rows/cols are fixed reference values, not per-cell storage
        rows, cols = len(board), len(board[0])

        # sc: O(k), holds found words, k = number of matching words
        # sc: O(L), holds cells currently on the path, L = max word length
        res, visit = set(), set()

        def dfs(r, c, node, path):

            # Path 1:
            # cell is outside the grid, this direction can't be explored
            if r < 0 or c < 0 or r >= rows or c >= cols:
                return

            # Path 2:
            # current board character isn't a valid next step in the Trie,
            # this path can never spell out a word from 'words'
            if board[r][c] not in node.subtrees:
                return

            # Path 3:
            # cell already used earlier in this same path, avoid reuse
            if (r, c) in visit:
                return

            # Choose:
            # mark current cell as visited and step into its Trie subtree
            visit.add((r, c))
            node = node.subtrees[board[r][c]]
            path += board[r][c]

            # New Valid word:
            # this node marks the end of a word in the Trie, record the path
            if node.isWord:
                res.add(path)

            # Explore:
            # recurse in all 4 directions, still bounded by the current Trie node
            # tc: O(4^L) total recursive calls in the worst case, L = max word length
            for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                dfs(r + dr, c + dc, node, path)

            # Backtrack:
            # remove current cell from visited so other paths can reuse it
            visit.remove((r, c))

        # Try starting DFS from every cell on the board
        # tc: O(rows * cols) starting points
        for r in range(rows):
            for c in range(cols):
                dfs(r, c, root, "")

        # overall: tc O(rows * cols * 4^L), L = max word length
        # overall: sc O(W + L), W = total characters across all words (Trie size)
        return list(res)

class TrieNode:
    def __init__(self):
        # sc: O(1) per node, grows to O(sum of word lengths) across whole Trie
        # dict of char subtrees for current node: char -> TrieNode
        self.subtrees = {}
        # stores the complete word at its end node, None if not a word end
        self.word = None


class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:

        # Backtracking + Trie:
        # Same core idea as Solution 1 -- DFS from every cell, only continuing
        # a path while it matches a valid prefix in the Trie built from 'words'.

        # Optimization vs Solution 1:
        #   1. In-place marking: instead of a separate 'visit' set, we
        #      temporarily overwrite the board cell itself ('#'), avoiding the
        #      extra O(L) set and its hashing overhead per cell.
        #   2. Leaf pruning: once a Trie subtree has no children left (every
        #      word through it has already been found), we delete it from its
        #      parent. This shrinks the Trie as words are found, so later DFS
        #      calls stop earlier instead of re-exploring dead branches.

        # sc: O(sum of len(word) for word in words), Trie holds every word's characters
        root = TrieNode()
        for word in words:
            node = root
            for c in word:

                # if subtree does not exist, create
                if c not in node.subtrees:
                    node.subtrees[c] = TrieNode()

                # iterate to subtree
                node = node.subtrees[c]

            # store complete word at its end node
            node.word = word

        # sc: O(1), rows/cols are fixed reference values, not per-cell storage
        rows, cols = len(board), len(board[0])

        # sc: O(k), holds found words, k = number of matching words
        result = []

        def dfs(r: int, c: int, parent: TrieNode):

            # grab curr char and its Trie node
            letter = board[r][c]
            curr_node = parent.subtrees[letter]

            # New Valid word:
            # this node marks the end of a word, record it and clear it out
            # to prevent the same word being added again via another path
            if curr_node.word:
                result.append(curr_node.word)
                curr_node.word = None

            # Choose:
            # mark current cell as visited in place, so it can't be reused
            # later in this same path
            board[r][c] = "#"

            # Explore:
            # recurse in all 4 directions, only into cells that are both
            # in-bounds and still a valid next character in the Trie
            # tc: O(4^L) total recursive calls in the worst case, L = max word length
            for (dr, dc) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:

                (nr, nc) = r + dr, c + dc

                if (0 <= nr < rows and
                    0 <= nc < cols and
                    board[nr][nc] in curr_node.subtrees):
                    dfs(nr, nc, curr_node)

            # Backtrack:
            # restore original cell value so other paths can reuse it
            board[r][c] = letter

            # Leaf Pruning:
            # if this Trie node has no remaining subtrees (every word through
            # it has already been found), remove it from its parent so future
            # DFS calls stop here immediately instead of descending into a
            # now-dead branch
            if not curr_node.subtrees:
                parent.subtrees.pop(letter)

        # Process Choices:
        # only start DFS from cells that match a valid first character in the Trie
        # tc: O(rows * cols) starting points
        for r in range(rows):
            for c in range(cols):
                if board[r][c] in root.subtrees:
                    dfs(r, c, root)

        # overall: tc O(rows * cols * 4^L), L = max word length, same bound as Solution 1
        # overall: sc O(W), W = total characters across all words (Trie size), no separate visited set
        return result

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

        # Backtracking:
        # Recursive function will build partitions incrementally, by using
        # DFS to try every possible next substring and only continuing a
        # branch while that substring is a palindrome.

        # sc: O(n) worst case, holds all valid partitions
        res = []

        # sc: O(n), holds current partition during recursion, max length n
        path = []

        def isPalindrome(l, r) -> bool:

            # Check candidate substring s[l:r+1] from both ends inward
            # tc: O(n) per call in the worst case
            while l < r:
                if s[l] != s[r]:
                    return False
                l += 1
                r -= 1
            return True

        def dfs(start):

            # New Valid partition:
            # reached end of string, every character has been partitioned
            if start == len(s):
                res.append(path[:])
                return

            # Path 1:
            # try every substring starting at 'start', extending one char at a time
            for end in range(start, len(s)):

                # Early Pruning:
                # only continue this branch if the candidate substring is a palindrome
                # tc: O(n) per check
                if isPalindrome(start, end):

                    # Choose:
                    # add palindromic substring to path
                    path.append(s[start:end + 1])

                    # Explore:
                    # recurse starting right after this substring
                    dfs(end + 1)

                    # Backtrack:
                    # remove last substring to try the next end position
                    path.pop()

        # Start backtracking at "root"
        dfs(0)

        # overall: tc O(n * 2^n), 2^n possible partitions worst case, each palindrome check O(n)
        # overall: sc O(n), recursion stack + path (auxiliary, excluding output)
        return res

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

        # Backtracking:
        # Same traversal shape as Solution 1 -- build partitions incrementally
        # via DFS, only continuing a branch while the candidate substring is
        # a palindrome.

        # Optimization vs Solution 1:
        # Solution 1 re-checks whether a substring is a palindrome from
        # scratch every time it's considered, O(n) per check, even though the
        # same substrings get re-examined across different branches. Here we
        # precompute every substring's palindrome status once in O(n^2) using
        # DP, so each check during backtracking becomes an O(1) lookup.

        n = len(s)

        # sc: O(n) worst case, holds all valid partitions
        res = []

        # sc: O(n), holds current partition during recursion, max length n
        path = []

        # sc: O(n^2), isPal[i][j] is True if s[i:j+1] is a palindrome
        isPal = [[False] * n for _ in range(n)]

        # Backwards -> Forwards:
        # to compute isPal[0][4], we need isPal[1][3] already known.
        # Looping i backwards ensures that by the time we reach row i,
        # row i + 1 (all substrings starting one index later) is already filled in.

        # tc: O(n^2), every substring checked exactly once
        for i in range(n - 1, -1, -1):
            for j in range(i, n):

                # Substring Length:
                # (j - i + 1) <= 3 covers base cases directly: "a", "aa", "aba"

                # Inner Substring:
                # if s[i+1:j] is a palindrome and the outer characters match,
                # then s[i:j+1] is also a palindrome
                if s[i] == s[j] and ((j - i + 1) <= 3 or isPal[i + 1][j - 1]):
                    isPal[i][j] = True

        def dfs(start):

            # New Valid partition:
            # reached end of string, every character has been partitioned
            if start == n:
                res.append(path[:])
                return

            # Path 1:
            # try every substring starting at 'start', extending one char at a time
            for end in range(start, n):

                # Early Pruning:
                # O(1) table lookup instead of Solution 1's O(n) re-scan
                if isPal[start][end]:

                    # Choose:
                    # add palindromic substring to path
                    path.append(s[start:end + 1])

                    # Explore:
                    # recurse starting right after this substring
                    dfs(end + 1)

                    # Backtrack:
                    # remove last substring to try the next end position
                    path.pop()

        # Start backtracking at "root"
        dfs(0)

        # overall: tc O(n^2 + n * 2^n), O(n^2) to build the table, O(n * 2^n) worst case for backtracking
        # overall: sc O(n^2), dominated by the palindrome table (recursion stack + path are O(n))
        return res

    def letterCombinations(self, digits: str) -> List[str]:

        # Backtracking:
        # Recursive function will build letter combinations incrementally,
        # by using DFS to try every letter mapped to the current digit,
        # one digit position at a time.

        # Path 1:
        # empty input has no digits to map, no combinations possible
        if not digits:
            return []

        # sc: O(1), fixed mapping of 8 digits to their letters
        digit_map = {
            "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
            "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
        }

        # sc: O(4^n * n) worst case, up to 4^n combinations each of length n
        res = []

        # sc: O(n), holds current combination during recursion, max length n = len(digits)
        path = []

        def dfs(index):

            # New Valid combination:
            # path length matches digits length, every digit has been mapped
            # tc: O(n) to join path into a string
            if index == len(digits):
                res.append("".join(path))
                return

            # Path 2:
            # try every letter mapped to the digit at this position
            # tc: O(4) per call, bounded by max letters per digit (7 and 9 map to 4)
            for char in digit_map[digits[index]]:

                # Choose:
                # add letter to path
                path.append(char)

                # Explore:
                # recurse to the next digit position
                dfs(index + 1)

                # Backtrack:
                # remove last letter to try the next option via the for loop
                path.pop()

        # Start backtracking at "root"
        dfs(0)

        # overall: tc O(4^n * n), n = len(digits), up to 4 choices per digit, n chars to join per combination
        # overall: sc O(n), recursion stack + path (auxiliary, excluding output)
        return res

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

        # Backtracking:
        # Recursive function will place one queen per row incrementally,
        # by using DFS to try every column in the current row and only
        # continuing a branch while that placement doesn't threaten any
        # queen already placed in an earlier row.

        # sc: O(n) worst case, holds all valid board configurations
        res = []

        # sc: O(n^2), n x n board
        board = [["."] * n for _ in range(n)]

        # 3 Sets to track threatened positions:

        # sc: O(n), columns currently occupied
        cols = set()
        # rows are inherently tracked by recursion depth, no separate set needed

        # sc: O(n), r - c diagonals: all cells on this diagonal share the same row - col value
        diag1 = set()
        # sc: O(n), r + c diagonals: all cells on this diagonal share the same row + col value
        diag2 = set()

        def dfs(row: int):

            # New Valid board:
            # every row has a queen placed, record this board configuration
            # tc: O(n^2) to join board into strings
            if row == n:
                res.append(["".join(r) for r in board])
                return

            # Path 1:
            # try every column in the current row
            for col in range(n):

                # Early Pruning:
                # skip this column if it or either diagonal is already threatened
                if col in cols or (row - col) in diag1 or (row + col) in diag2:
                    continue

                # Choose:
                # place queen at (row, col), mark column and both diagonals occupied
                board[row][col] = "Q"
                cols.add(col)
                diag1.add(row - col)
                diag2.add(row + col)

                # Explore:
                # recurse to the next row, row + 1 guarantees rows never overlap
                dfs(row + 1)

                # Backtrack:
                # remove queen and free column/diagonals to try the next column
                board[row][col] = "."
                cols.remove(col)
                diag1.remove(row - col)
                diag2.remove(row + col)

        # Start backtracking at "root", row 0
        dfs(0)

        # overall: tc O(n!), n choices in row 0, at most n-1 in row 1, pruned further by diagonals
        # overall: sc O(n^2), board dominates; cols/diag1/diag2/recursion stack are each O(n)
        return res

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

        # Backtracking:
        # Same traversal shape as Solution 1 -- place one queen per row via
        # DFS, only continuing while the placement doesn't threaten an
        # earlier queen -- but threatened positions are tracked with integer
        # bitmasks instead of three separate sets.

        # Optimization vs Solution 1:
        # Solution 1's set lookups (col in cols, etc.) and the n x n board
        # array add overhead per check and per placement. Here, 'cols',
        # 'diag1', and 'diag2' are single integers where each bit represents
        # a threatened column/diagonal position. Combining them with bitwise
        # OR and checking availability with a single AND/NOT turns each row's
        # "which columns are free" computation into O(1) bitwise ops instead
        # of n individual set lookups, and shifting diag1/diag2 by 1 each row
        # naturally re-aligns them for the next row without recomputing from
        # row/col arithmetic.

        # sc: O(n) worst case, holds all valid board configurations
        res = []

        # sc: O(n), holds chosen column index per row during recursion
        path = []

        def dfs(row, cols, diag1, diag2):

            # New Valid board:
            # every row has a queen placed, convert path (row -> column) into board strings
            # tc: O(n^2) to build the board
            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

            # Path 1:
            # compute every column in this row that's not threatened, as a bitmask
            # tc: O(1) bitwise ops instead of n individual set lookups
            available = ((1 << n) - 1) & (~(cols | diag1 | diag2))

            # try every available column, extracting the lowest set bit each time
            while available:

                # Choose:
                # isolate the rightmost available bit and remove it from 'available'
                pos = available & -available
                available &= available - 1
                col = (pos - 1).bit_length()

                path.append(col)

                # Explore:
                # recurse to the next row with updated masks; diag1/diag2 shift by
                # one bit to stay aligned with the diagonal's position on the next row
                dfs(row + 1, cols | pos, (diag1 | pos) << 1, (diag2 | pos) >> 1)

                # Backtrack:
                # remove last chosen column, cols/diag1/diag2 are never mutated in
                # place (new masks are passed per call), so nothing else to undo
                path.pop()

        # Start backtracking at "root", row 0, no columns/diagonals threatened yet
        dfs(0, 0, 0, 0)

        # overall: tc O(n!), same combinatorial bound as Solution 1, fewer constant-factor ops per check
        # overall: sc O(n), no n x n board maintained during recursion, only path + bitmask args
        return res

    def solveSudoku(self, board: List[List[str]]) -> None:

        # Backtracking:
        # Same traversal shape as Solution 1 -- fill empty cells incrementally
        # via DFS, trying every digit 1-9 and only keeping placements that
        # satisfy the row, column, and 3x3 box constraints.

        # Optimization vs Solution 1:
        # Solution 1's isValid() rescans the entire row, column, and box from
        # scratch on every single check, O(n) per check. Here we instead
        # maintain three sets of "digits already used" -- one per row, one
        # per column, one per box -- updated incrementally as digits are
        # placed and removed. This turns each validity check into an O(1)
        # set lookup instead of an O(n) scan, which is what actually matters
        # for passing within LeetCode's time limit on this problem.

        n = 9

        # sc: O(n), one set per row tracking digits already placed in that row
        rows = [set() for _ in range(n)]

        # sc: O(n), one set per column tracking digits already placed in that column
        cols = [set() for _ in range(n)]

        # sc: O(n), one set per 3x3 box tracking digits already placed in that box
        boxes = [set() for _ in range(n)]

        # sc: O(m), list of empty cell coordinates to fill, m = number of empty cells
        empties = []

        # Preprocess board: seed rows/cols/boxes sets and collect empty cells
        # tc: O(n^2), fixed 81-cell scan regardless of input
        for r in range(n):
            for c in range(n):
                digit = board[r][c]
                if digit == '.':
                    empties.append((r, c))
                else:
                    b = (r // 3) * 3 + c // 3
                    rows[r].add(digit)
                    cols[c].add(digit)
                    boxes[b].add(digit)

        def dfs(idx: int) -> bool:

            # New Valid board:
            # every empty cell has been filled validly
            if idx == len(empties):
                return True

            row, col = empties[idx]
            b = (row // 3) * 3 + col // 3

            # Path 1:
            # try every digit 1-9 in this empty cell
            # tc: O(9) per call, bounded by fixed digit range
            for digit in "123456789":

                # Early Pruning:
                # O(1) set lookups instead of Solution 1's O(n) row/col/box scan
                if digit in rows[row] or digit in cols[col] or digit in boxes[b]:
                    continue

                # Choose:
                # place digit on board and mark it used in all three constraint sets
                board[row][col] = digit
                rows[row].add(digit)
                cols[col].add(digit)
                boxes[b].add(digit)

                # Explore:
                # recurse to the next empty cell, if this eventually completes
                # the whole board, propagate success back up immediately
                if dfs(idx + 1):
                    return True

                # Backtrack:
                # digit didn't lead to a solution, revert cell and all three
                # constraint sets, then try the next digit via the for loop
                board[row][col] = '.'
                rows[row].discard(digit)
                cols[col].discard(digit)
                boxes[b].discard(digit)

            # Exhausted: no digit works at this cell, this branch has failed
            return False

        # Start backtracking at the first empty cell, mutates board in place
        dfs(0)

        # overall: tc O(9^m), m = number of empty cells, each check now O(1) instead of O(n)
        # overall: sc O(m), recursion stack depth + rows/cols/boxes sets
        return