Backtracking

# Time complexity: O(N * 4^N) where N = length of digits
# Space complexity: O(N * 4^N)
#   The extra N is due to string contatenation.
def letterCombinations(digits: str) -> List[str]:
    if not digits:
        return []

    chars = {
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "pqrs",
        "8": "tuv",
        "9": "wxyz"
    }

    answer = []
    dfs(digits, chars, answer, "")
    return answer

def dfs(digits, chars, answer, currStr) -> None:
    if len(currStr) >= len(digits):
        answer.append(currStr)
        return

    # len(currStr) corresponds with current index of digits
    for c in chars[digits[len(currStr)]]:
        dfs(digits, chars, answer, currStr + c)

Alternative solution:

from collections import deque

# Time complexity: O(N * 4^N) where N = length of digits
# Space complexity: O(N * 4^N)
def letterCombinations(digits: str) -> List[str]:
    if not digits:
        return []

    chars = {
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "pqrs",
        "8": "tuv",
        "9": "wxyz"
    }

    q = deque()
    q.append("")

    # Incrementally add chars to each string in q
    # Loop until q only contains strings with equal length to digits
    while len(q[0]) != len(digits):
        currStr = q.popleft()
        # Length of currStr corresponds with current index of digits
        # E.g. currStr = "d"; digits = "357" -> loop through chars[5]
        for c in chars[digits[len(currStr)]]:
            q.append(currStr + c)

    return q

# Time complexity: O(c(n, k) * k)
# Space complexity: O(c(n, k) * k)
def combine(n: int, k: int) -> List[List[int]]:
    answer = []
    helper(n, k, answer, [], 1)
    return answer

def helper(n, k, answer, currLi, currVal) -> None:
    if len(currLi) == k:
        # Need copy of list due to passing by reference
        answer.append(currLi[:])
        return

    # Faster loop compared to range(currVal, n + 1)
    # Suppose n = 10, k = 5, currLi = []
    # If i = 7, the largest possible currLi will be [7, 8, 9, 10],
    #   which is not a valid answer.
    # (n - (k - len(currLi)) + 2) cuts off unnecessary recursion.
    for i in range(currVal, n - (k - len(currLi)) + 2):
        currLi.append(i)
        helper(n, k, answer, currLi, i + 1)
        currLi.pop()

# Time complexity: O(n * n!)
# Space complexity: O(n * n!)
def permute(nums: List[int]) -> List[List[int]]:
    answer = []
    helper(nums, answer, [], set())
    return answer

def helper(nums, answer, currLi, currSet) -> None:
    if len(currLi) == len(nums):
        answer.append(currLi[:])
        return

    for i in range(len(nums)):
        # Loop through every element that isn't in currLi
        if nums[i] not in currSet:
            currLi.append(nums[i])
            currSet.add(nums[i])
            helper(nums, answer, currLi, currSet)
            currLi.pop()
            currSet.remove(nums[i])

# Time complexity: O(N * 2^(M)) where N = length of currLi; M = sum of (target / candidate[i]) for all candidates
# Space complexity: O(K) where K = length of longest combination
def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
    answer = []
    helper(candidates, target, answer, [], 0, 0)
    return answer

def helper(candidates, target, answer, currLi, currSum, index):
    if currSum > target:
        return

    if currSum == target:
        answer.append(currLi[:])
        return

    # All solutions containing elements before index have been checked
    for i in range(index, len(candidates)):
        currLi.append(candidates[i])
        # Recurse with same index because answer allows duplicates
        helper(candidates, target, answer, currLi, currSum + candidates[i], i)
        currLi.pop()

# Time complexity: O(2^n)
# Space complexity: O(n)
def generateParenthesis(n: int) -> List[str]:
    answer = []
    helper(n, answer, [], 0, 0)
    return answer

def helper(n, answer, currLi, openCount, closeCount):
    # There can at most be n open parentheses,
    # and close parentheses cannot exceed open
    if openCount > n or closeCount > openCount:
        return

    if n == openCount and openCount == closeCount:
        answer.append("".join(currLi))
        return

    currLi.append("(")
    helper(n, answer, currLi, openCount + 1, closeCount)
    currLi.pop()

    currLi.append(")")
    helper(n, answer, currLi, openCount, closeCount + 1)
    currLi.pop()

# Time complexity: O(n * m * 4^k) where n, m = board dimensions; k = length of word
# Space complexity: O(k)
def exist(board: List[List[str]], word: str) -> bool:
    for r in range(len(board)):
        for c in range(len(board[0])):
            if board[r][c] != word[0]:
                continue
            if helper(board, word, 0, r, c):
                return True
    return False

def helper(board, word, index, row, col) -> bool:
    if row < 0 or row >= len(board) or col < 0 or col >= len(board[0]):
        return False
    if board[row][col] != word[index]:
        return False

    if index == len(word) - 1:
        return True

    board[row][col] = ""  # Mark as visited
    found = (
        helper(board, word, index + 1, row - 1, col) or
        helper(board, word, index + 1, row, col + 1) or
        helper(board, word, index + 1, row + 1, col) or
        helper(board, word, index + 1, row, col - 1)
    )
    board[row][col] = word[index]  # Revert visited
    return found