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 1: Hit All Path Max Depths
        # Recursive function that builds a solution incrementally,
        # exploring all possible choices at each step.

        # Determining Backtracking Complexity:
        # For backtracking, we can determine the complexity by seeing how many choices 
        # we have at a branch,
        # for this we have the 2 options of 1. adding or 2. not adding a number to the path,
        # and we have this choice for n numbers, 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, they are still references to the same objects.
        # if a an object like school, had inner student objects, if we copied the school object, 
        # the new object would still refer to the original student objects
        # Since we are dealing with integers, a deep copy is not required, shallow is fine,
        # but it is interesting to note that different path objects will be sharing the same
        # reference to integer objects, but again, this is fine since in python 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 Path:
        # Follows the standard choose -> explore -> unchoose pattern:
        #   1. Choose: add a number to the current path
        #   2. Explore: recurse to build further subsets from the next index
        #   3. Unchoose (Backtrack): remove the last number to restore state
        # The recursion continues until all valid subsets are generated.

        # 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 = []  

        # tc: O(n * 2^n)  2^n subsets, each copied (length <= n)
        # sc: O(n * 2^n)  2^n subsets, each stores (length <= n) + recursion stack O(n) overruled
        def dfs_backtrack(start: int):
            
            # Process Root: Check 1 Base Case

            # Base Case 1: add subset
            # add current subset (shallow copy) to full subset list
            # tc: O(n) for copy of path (max length n)
            # sc: O(n) added to result
            res.append(path[:])

            # Process Choices:
            # tc: iterate over n
            for i in range(start, len(nums)):
                
                # Choose:
                # build next path, append number to current path
                # tc: O(1), sc: O(1)
                path.append(nums[i])

                # Explore:
                # recurse to build further subsets
                # use next index to avoid reusing current number candidate
                # tc: O(2^n) total recursive calls (all possible subsets)
                dfs_backtrack(i+1)

                # Unchoose: Backtrack 
                # remove last number to explore next choice
                # tc: O(1), sc: O(1)
                path.pop()

        # Initial call, no path passed
        dfs_backtrack(0)

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

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

        # Backtracking 1: Hit All Path Max Depths
        # Recursive function that builds a solution incrementally,
        # exploring all possible choices at each step.

        # Generator / Yield vs Result List:
        # In traditional backtracking (like Solution 1 and 3), we store all subsets
        # in a list 'res'. Each valid subset is copied and added to 'res', so memory
        # usage grows proportional to the total number of subsets (O(n * 2^n)).
        #
        # 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), independent of the total number of subsets.
        # The caller may still store the subsets if desired, but inside the function
        # itself, no large list of all subsets is maintained.

        # Generator / Yield Auxiliary space (not counting the output):
        # Only the current path and recursion stack are in memory, O(n) instead of O(n * 2^n)
        # yield reduces memory used inside the function itself, because it doesn't 
        # have to store all results within res.
        # Usually, all paths would exist at the same time, however 'yield' allows us to produce subsets
        # one at a time instead of storing them all in a list that gets passed around

        # Mutable path list used to build subsets
        # sc: O(n) holds the current path (max depth = n)
        path = []

        def dfs_backtrack(start: int):

            # 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])

                # Recurse New Path:
                # Recurse with next index to avoid duplicates and reuse
                # tc: O(2^n) total recursive calls
                # sc: recursion stack O(n)
                yield from dfs_backtrack(i + 1)

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

        # Initial call, no path passed
        # tc: O(1) to create generator
        # sc: O(1) auxiliary for the generator object itself
        res = dfs_backtrack(0)

        # At this point:
        # - res is NOT a list of subsets
        # - res is a generator object (think of it like a paused function)
        # - no subsets have been stored yet
        # - only the dfs_backtrack function definition exists and can produce values

        # To get subsets, we need to consume the generator:
        #
        # 1. Iterate over it directly:
        #   for subset in res:
        #         print(subset)        ->   subsets are generated one by one
        #
        # 2. Convert to list to store all subsets in memory:
        #   all_subsets = list(res)    ->   now all subsets are generated and stored

        # overall: tc O(n * 2^n)          # must generate all subsets, each copied
        # overall: sc O(n)                # auxiliary, recursion stack + path
        # overall: sc O(n * 2^n)          # including storing all subsets (if caller stores them)
        return res

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

        # Backtracking 1: Hit All Path Max Depths
        # Iterative function that builds a solution incrementally,
        # exploring all possible choices at each step.

        # Determining Backtracking Complexity:
        # For backtracking, we can determine the complexity by seeing how many choices 
        # we have at a branch,
        # for this we have the 2 options of 1. adding or 2. not adding a number to the path,
        # and we have this choice for n numbers, so we get 2^n 

        # Backtracking Path:
        # Follows the standard choose -> explore -> unchoose pattern:
        #   1. Choose: add a number to the current path
        #   2. Explore: form new subsets by including this number in all existing subsets
        #   3. Unchoose: implicit, as original subsets remain unchanged
        # Continues until all valid subsets are generated.

        # Process Root: Check 1 Base Case

        # Base Case: Empty Subset
        # first valid subset is the empty subset
        # sc: O(n * 2^n) 2^n subsets each length up to n
        res = [[]]

        # Process Choices: 
        # tc: iterate over n O(n)
        for n in nums:

            # Grab all current paths:
            # New paths will be build upon current paths, grab current paths
            currentSubsetNum = len(res)
            # tc: iterate over 2^n subsets O(2^n)
            for i in range(currentSubsetNum):

                # Choose:
                # build new path, new subset by adding number to an existing subset
                # tc: O(n) for copy of path length n
                # sc: O(n) for new string of length n
                newSubset = res[i] + [n]

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

                # Explore:
                # append new subset to result list, will be explored in future iterations
                # tc: O(n) for copy of path (max length n)
                # sc: O(n) added to result                
                res.append(newSubset)

                # Unchoose (backtrack):
                # implicit, original smaller subsets remain unchanged in res list,
                # will be used in future iterations 

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

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        
        # Backtracking 2: Pruning Invalid Solutions
        # Recursive function that builds a solution incrementally,
        # exploring only choices that can still lead to a valid solution.
        
        # When a partial solution violates constraints (in this case, sum > target),
        # the recursion stops immediately and prunes the branch
        # instead of continuing to explore further.
        # This reduces the search space compared to full backtracking,
        # improving practical runtime while preserving correctness.
        # Time complexity remains exponential in the worst case,
        # where all paths end up being valid,
        # but pruning lowers the effective branching factor.
        # Space complexity is O(depth) due to the recursion call stack.

        # Late Pruning:
        # Candidates are added first, and only then pruned within the branch itself.
        # This creates more branches than early pruning solutions, as invalid branches
        # are explored first and only pruned after exceeding constraints.

        # Backtracking (DFS) with Late Pruning:
        # Recursive function that builds solutions incrementally using a global path.
        # Follows the standard choose -> explore -> unchoose pattern:
        #   1. Choose: add a candidate to the current path
        #   2. Explore: recurse to build further choices from the current index (reuse allowed)
        #       - Process current root:
        #       - Check if the current sum equals the target
        #       - Late Pruning: stop recursion if the current sum exceeds the target
        #   3. Unchoose (Backtrack): remove the last candidate to restore state
        # Result: all valid combinations are appended to the result list

        # sc: O(1) initially, grows as valid combinations are added
        res = []

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

        def dfs_backtrack(start, currSum):

            # Process Root: Check 2 Base Cases

            # Base Case 1: target found
            if currSum == target:

                # tc: O(depth) for shallow copy
                # sc: O(depth) added to result
                res.append(path[:])
                return

            # Base Case 2: late branch pruning
            # Check: if sum is exceeds the target
            # Then: prune future branches and return
            # tc: O(1)
            # sc: O(1)
            if currSum > target:
                return

            # Process Choices:

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

                # tc: O(1), sc: O(1)
                candidate = candidates[i]

                # Choose: 
                # build next path
                # tc: O(1), sc: O(1)
                path.append(candidate)

                # Explore:
                # recurse with same index (allowing reuse of current candidate)
                # tc: up to n recursive calls per level, max depth ~ target / min_cand
                # tc: O(n^(target/min_cand)) in worst case
                dfs_backtrack(i, currSum + candidate)

                # Unchoose: backtrack:
                # remove last candidate
                # tc: O(1), sc: O(1)
                path.pop()

        # Start recursion from index 0 with sum 0
        # tc: O(n^(target/min_cand)), sc: O(target/min_cand) recursion stack
        dfs_backtrack(0, 0)

        # overall: tc O(n^(target/min_cand))
        # overall: sc O(target/min_cand + output size)
        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 generateParenthesis(self, n: int) -> List[str]:
        
        # generates all possible combinations of n pairs of parentheses
        def generate_combinations(current, length, combinations):
            
            # base case: if 
            if length == 2 * n:
                combinations.append(current)
                return

            # recursively add '(' and ')' to the current string to generate all possible combinations
            generate_combinations(current + "(", length + 1, combinations)
            generate_combinations(current + ")", length + 1, combinations)

        # checks if given parentheses string is valid
        def isValid(s: str) -> bool:
            # counter to track balance of parentheses
            balance = 0

            # iterate through parentheses string
            for char in s:
                
                # increment balance
                if char == '(':
                    balance += 1
                # decrement balance
                else:
                    balance -= 1
                # closing parenthesis has no matching
                if balance < 0:
                    return False

            # validate all parentheses have match
            return balance == 0

        # grab all possible combinations
        combinations = []
        generate_combinations("", 0, combinations)

        result = []
        
        # generate and validate all combinations
        for combo in combinations:
            if isValid(combo):
                result.append(combo)
        
        # overall: time complexity
        # overall: space complexity
        return result

    def generateParenthesis(self, n: int) -> List[str]:
        
        # Initialize a stack to simulate depth-first search (DFS)        
        # (currString, openParenCount, closedParenCount)
        stack = [("", 0, 0)]
        result = []

        # while stack is non-empty
        while stack:

            # 
            current, openCount, closeCount = stack.pop()

            # if we have a valid combination of n '(' and n ')' add to list
            if openCount == n and closeCount == n:
                result.append(current)
                continue

            # INCORRECT: condition allows ')' to be added even if they exceed the number of '('
            # should be `closeCount < openCount`
            if closeCount < n:
                stack.append((current + ")", openCount, closeCount + 1))
            if openCount < n:
                stack.append((current + "(", openCount + 1, closeCount))

        # overall: time complexity
        # overall: space complexity
        return result

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

        def helper(curr, open_count, close_count):

            if open_count + close_count == (2*n):
                res.append("".join(curr))
                return

            if open_count < n:
                curr.append('(')
                helper(curr, open_count + 1, close_count)
                curr.pop()
            
            # INCORRECT:
            # we only want to add a closing parentheses if the closed count 
            # is less than the opening parentheses count
            # to ensure that every closed has a matching open
            # Instead:
            # if close_count < open_
            else:
                curr.append(')')
                helper(curr, open_count, close_count + 1)
                curr.pop()

            
        helper([], 0, 0)

        return res

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

        def helper(curr, open_paren, close_paren):

            if open_paren == n and close_paren == n:
                res.append("".join(curr))
                return

            if open_paren < n:
                curr.append('(')
                helper(curr, open_paren + 1, close_paren)
                curr.pop()
            
            # INCORRECT:
            # the two if statements should be mutually exclusive
            # we do not one to skip the elif, when the if is true
            # Instead:
            # if close_paren < open_paren
            elif close_paren < open_paren:
                curr.append(')')
                helper(curr, open_paren, close_paren + 1)
                curr.pop()

        helper([], 0, 0)

        return res

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

        def helper(curr, open_count, close_count):

            if open_count + close_count == (2*n):
                res.append("".join(curr))
                return

            if open_count < n:
                # INCORRECT:
                # treating list as string
                # list.append() modifies the list in-place and returns None.
                # So curr.append('(') does append the character, but returns None
                # instead:
                # curr.append()
                # helper(curr, open_count + 1, close_count)
                # curr.pop()
                helper(curr.append('('), open_count + 1, close_count)

            if close_count < open_count:
                # INCORRECT:
                # treating list as string
                # list.append() modifies the list in-place and returns None.
                # So curr.append('(') does append the character, but returns None
                # instead:
                # curr.append()
                # helper(curr, open_count + 1, close_count)
                # curr.pop()
                helper(curr.append(')'), open_count, close_count + 1)

        stack = []
        helper(stack, 0, 0)

        return res

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

        # Note:
        # Explicit stack simulates backtracking process iteratively.
        # Each stack element stores the current string and counts of open and closed parentheses.
        # Allows state tracking without recursion.

        # Store valid parentheses
        result = []

        # Tracks state (current_string, open_count, closed_count)
        stack = [([], 0, 0)] 

        # Simulate backtracking
        # time complexity: each state processed once, building up to O(Catalan(n)) strings
        # space complexity: stack can grow to O(Catalan(n)), result stores O(Catalan(n)) strings
        while stack:

            # Pop current state, current state is explored only once
            curr, openCount, closeCount = stack.pop()

            # Base case: reached valid string
            if openCount == n and closeCount == n:
                result.append("".join(curr))
                continue

            # Check: open count is less than total expected
            # Ensures: string is always valid, with total number of parens being valid
            # Iterative step 1: add '('
            if openCount < n:
                
                # INCORRECT:
                # since there is only 1 curr,
                # appending will affect all branches
                # Instead:
                # make a copy
                # new_curr = curr + ['(']
                curr.append('(')
                stack.append((curr, openCount + 1, closeCount))

            # Check: closed count is less than open count
            # Ensures: string is always valid, with each open having a matching close
            # Iterative step 2: add '('
            if closeCount < openCount:
                # INCORRECT:
                # since there is only 1 curr,
                # appending will affect all branches
                # Instead:
                # make a copy
                # new_curr = curr + ['(']
                curr.append(')')
                stack.append((curr, openCount, closeCount + 1))

        # overall: time complexity O(Catalan(n) * n)
        # overall: space complexity O(Catalan(n) * n)
        return result

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

        dp = [[] for i in range (n+1)]

        # INCORRECT:
        # dp is never initialized, so it can never be built upon
        # Instead:
        # dp[0] = [""]

        # generate for level i pairs
        for i in range(n+1):

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

                # forward iteration
                for left in dp[j]:
                    # backward iteration
                    for right in dp[i - 1 - j]:
                        dp[i].append(f"({left}){right}")


        return dp[n]

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

        res = []

        def helper(currList, openCount, closedCount):

            if openCount + closedCount == (2*n):
                res.append("".join(currList))
                return

            if openCount < n:
                currList.append("(")
                helper(currList, openCount+1, closedCount)
                currList.pop()

            if closedCount < openCount:
                currList.append(")")
                
                # INCORRECT:
                # closed count was not updated
                # Instead:
                # helper(currList, openCount, closedCount + 1)
                helper(currList, openCount, closedCount)
                currList.pop()

        
        helper([], 0, 0)

        return res

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

        # INCORRECT:
        # Instead:
        # dp = [[] for i in range(n+1)]
        dp = [] * (n+1)

        dp[0] = [""]

        for i in range(n+1):

            for j in range(i):

                for left in dp[j]:
                    for right in dp[i-1-j]:
                        dp[i].append(f"({left}){right}")

        return dp[n]

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

        # String Immutability:
        # Every time we do current + "(" in python a new string is created
        # and the entire contents of current are copied.
        # Since this happens at every recursion level and there are Catalan(n) valid sequences,
        # the time becomes O(Catalan(n) * n^2)
        # due to copying. 
        # Solution 2 has a time of O(Catalan(n) * n), this is here to show the slow version

        # Temporary/Working Memory:
        # We also use more memory with strings as along one recursion path we create ~n strings
        # each of up to length n, so peak temporary memory is O(n^2)
        # Solution 2 has temporary memory of O(n), since we have a single stack we are popping/appending from

        # Backtracking:
        # Explores all valid sequences of parentheses.
        # A new string is created on each recursive call using string 
        # concatenation for string length up to 2n leading to O(n^2).

        res = []

        # tc: each recursion path creates  explores a state; only leaf call does ''.join(), leading to O(n)
        # sc: call stack depth is O(n), string copying adds O(n) per leaf path, leading to O(n^2)
        def dfs_backtrack(current: List[str], num_open: int, num_closed: int):

            # Process Root: reached valid string 
            if len(current) == n * 2:
                res.append(current)
                return

            # Explore Choice 1: add '('
            # Check: open count is less than total expected
            # Implies: adding '(' will create valid string
            if num_open < n: 

                # Build: append open '('
                # tc: concat O(n)
                new_str = current + "("

                # Explore: recursion with new string copy
                dfs_backtrack(new_str, num_open + 1, num_closed)

                # Backtrack: no need to modify copy as original string still exists

            # Explore Choice 2: add ')'
            # Check: closed count is less than open count
            # Implied: adding ')' is required for valid string
            if num_closed < num_open:
                
                # Build: append close ')'
                # tc: concat per iteration O(n)
                new_str = current + ")"
    
                # Explore: recursion with new string copy
                dfs_backtrack(new_str, num_open, num_closed + 1)

                # Backtrack: no need to modify copy as original string still exists

        # Initial call, empty list passed
        dfs_backtrack("", 0, 0)

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

    def generateParenthesis(self, n: int) -> List[str]:
        
        # List Mutability:
        # We use a single list curr and modify it in place using append/pop.
        # Append() and pop() are both constant O(1) and no copying happens at each recursion step.
        # The list only gets converted once we have found a valid combination using "".join(curr).
        # Since there are Catalan(n) valid sequences 
        # the time becomes O(Catalan(n) * n) which is faster than the string version of O(Catalan(n) * n^2)

        # Temporary/Working Memory:
        # We use a single stack to track our changes, so peak temporary memory is O(n)

        # Backtracking:
        # Explores all valid sequences of parentheses.
        # Only when a complete sequence is found (length == 2 * n), 
        # we convert the list to a string via concat in O(n)

        res = []
        
        # tc: each recursion explores a state; only leaf call does ''.join(), leading to O(n)
        # sc: call stack depth O(n), current list holds up to 2n
        def dfs_backtrack(current, openCount, closeCount):

            # Base case: 
            # If we have used all open and close parentheses
            if openCount == n and closeCount == n:
                # tc: convert once at leaf for 2n length O(n)
                res.append("".join(current))
                return

            # Recursive case 1: add '('
            # Check: open count is less than total expected
            # Ensures: string is always valid, with total number of parens being valid
            if openCount < n: 

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

                # Explore: recurse with updated list
                helper(current, openCount + 1, closeCount)

                # Backtrack: remove last open '('
                current.pop()
            
            # Recursive case 1: add ')'
            # Check: closed count is less than open count
            # Ensures: string is always valid, with each open having a matching close
            if closeCount < openCount:

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

                # Explore: recurse with updated list
                helper(current, openCount, closeCount + 1)

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

        # Initial call, 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]:

        # Explicit Iterative Stack:
        # Simulates backtracking process iteratively by storing state on the stack.
        # Each state element holds the current string and counts of open and closed parentheses,
        # which allows state tracking without recursion

        # Store valid parentheses
        result = []

        # Tracks state (current_string, open_count, closed_count)
        stack = [([], 0, 0)] 

        # Simulate backtracking
        # tc: each state processed once, building up to O(Catalan(n)) strings
        # sc: stack can grow to O(Catalan(n)), result stores O(Catalan(n)) strings
        while stack:

            # Process Root:
            # Grab/pop current state from stack, current state is explored only once
            curr, openCount, closeCount = stack.pop()

            # Process Root: reached valid string
            if openCount == n and closeCount == n:
                result.append("".join(curr))
                continue

            # Explore Choice 1: add '('
            # Check: open count is less than total expected
            # Implies: we have space to add an open parenthesis
            if openCount < n:
                
                # Build: append open '('
                # Creating copy of list to avoid mutating other branches,
                # (cannot do curr.append('(') because that would modify the original list)
                new_curr = curr.copy()
                new_curr.append('(')

                # Explore: iterative recursion by putting new state on stack for future exploration
                stack.append((new_curr, openCount + 1, closeCount))

                # Backtrack:
                # No need to .pop() as the pop() from the stack will remove this new state eventually

            # Explore Choice 2: add ')'
            # Check: closed count is less than open count
            # Implies: we have a matching open for our closed parenthesis
            if closeCount < openCount:

                # Build: append close ')'
                # Creating copy of list to avoid mutating other branches,
                # (cannot do curr.append(')') because that would modify the original list)
                new_curr = curr + [')']

                # Explore: iterative recursion by putting new state on stack for future exploration
                stack.append((new_curr, openCount, closeCount + 1))

                # Backtrack:
                # No need to .pop() as the pop() from the stack will remove this new state eventually

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

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