Recursion

Table of Contents

• 46. Permutations (Medium)
• 78. Subsets (Medium)
• 17. Letter Combinations of a Phone Number (Medium)

46. Permutations

• LeetCode | LeetCode CH (Medium)

• Tags: array, backtracking

46. Permutations - Python Solution

from typing import List


# Backtracking
def permute(nums: List[int]) -> List[List[int]]:
    n = len(nums)
    path, res = [], []
    used = [False for _ in range(n)]

    def dfs(x: int):
        if x == n:
            res.append(path[:])
            return

        for i in range(n):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            dfs(x + 1)
            path.pop()
            used[i] = False

    dfs(0)

    return res


print(permute([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3],
#  [2, 3, 1], [3, 1, 2], [3, 2, 1]]

78. Subsets

• LeetCode | LeetCode CH (Medium)

• Tags: array, backtracking, bit manipulation

78. Subsets - Python Solution

from typing import List


# Iterative Inclusion Backtracking
def subsets_iterative_inclusion(nums: List[int]) -> List[List[int]]:
    n = len(nums)
    res, path = [], []

    def dfs(i):
        res.append(path.copy())

        for j in range(i, n):
            path.append(nums[j])
            dfs(j + 1)
            path.pop()

    dfs(0)

    return res


# Binary Decision Backtracking
def subsets_binary_decision(nums: List[int]) -> List[List[int]]:
    n = len(nums)
    res, path = [], []

    def dfs(i):
        if i == n:
            res.append(path.copy())
            return

        # Exclude
        dfs(i + 1)

        # Include
        path.append(nums[i])
        dfs(i + 1)
        path.pop()

    dfs(0)

    return res


print(subsets_iterative_inclusion([1, 2, 3]))
# [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
print(subsets_binary_decision([1, 2, 3]))
# [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

17. Letter Combinations of a Phone Number

• LeetCode | LeetCode CH (Medium)

• Tags: hash table, string, backtracking

• Return all possible letter combinations that the number could represent.

17. Letter Combinations of a Phone Number - Python Solution

from typing import List


# Backtracking
def letterCombinations(digits: str) -> List[str]:
    """Return all possible letter combinations that the number could represent.

    Args:
        digits (str): A string containing digits from 2-9 inclusive.

    Returns:
        List[str]: All possible letter combinations.

    Complexity:
        Time: O(4^n), where n is the number of digits in the input string.
        Space: O(4^n), where n is the number of digits in the input string.

    Example:
        >>> letterCombinations("23")
        ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
        >>> letterCombinations("")
        []
    """

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

    n = len(digits)
    if n == 0:
        return []

    res = []

    def dfs(idx, path):
        if idx == n:
            res.append(path)
            return None

        letters = letter_map[digits[idx]]

        for i in range(len(letters)):
            dfs(idx + 1, path + letters[i])

    dfs(0, "")

    return res


if __name__ == "__main__":
    import doctest

    doctest.testmod()

Comments