回溯 — 實戰題解

# python
# LC 17 - Letter Combinations of a Phone Number
# IDEA: one depth per digit; the choice list at depth i is the letters of digits[i]
# time = O(4^n * n), space = O(n)   n = len(digits); up to 4 letters per digit, O(n) to join each
def letterCombinations(digits):
    if not digits:
        return []                        # no digits: no combinations, not [""]
    letters = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
               "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
    res = []
    path = []

    def backtrack(i):
        if i == len(digits):             # one letter chosen for every digit
            res.append("".join(path))
            return
        for ch in letters[digits[i]]:
            path.append(ch)
            backtrack(i + 1)
            path.pop()                   # undo the LAST letter

    backtrack(0)
    return res

// java
// LC 17 - Letter Combinations of a Phone Number
// IDEA: one depth per digit; the choice list at depth i is the letters of digits[i]
// time = O(4^n * n), space = O(n)
private static final String[] LETTERS = {
    "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};

public List<String> letterCombinations(String digits) {
    List<String> res = new ArrayList<>();
    if (digits.isEmpty()) {
        return res;                                   // no digits: no combinations, not [""]
    }
    backtrack(digits, 0, new StringBuilder(), res);
    return res;
}

private void backtrack(String digits, int i, StringBuilder path, List<String> res) {
    if (i == digits.length()) {
        res.add(path.toString());
        return;
    }
    String choices = LETTERS[digits.charAt(i) - '0'];
    for (char ch : choices.toCharArray()) {
        path.append(ch);
        backtrack(digits, i + 1, path, res);
        path.deleteCharAt(path.length() - 1);         // undo the LAST char, not the first
    }
}

# python
# IDEA: iterative product: extend every partial combination by each letter of the next digit
# time = O(4^n * n), space = O(4^n * n)   every partial combination is kept
def letterCombinations(digits):
    if not digits:
        return []
    letters = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
               "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
    combos = [""]
    for digit in digits:
        extended = []
        for prefix in combos:
            for ch in letters[digit]:
                extended.append(prefix + ch)
        combos = extended
    return combos

# python
# LC 784 - Letter Case Permutation
# IDEA: fixed order, one decision per index: a letter branches two ways, a digit one way
# time = O(2^L * n), space = O(n)   L = letters in s; O(n) to join each answer
def letterCasePermutation(s):
    res = []
    path = []

    def backtrack(i):
        if i == len(s):
            res.append("".join(path))
            return
        ch = s[i]
        if ch.isalpha():
            options = [ch.lower(), ch.upper()]
        else:
            options = [ch]               # a digit has no choice to make
        for option in options:
            path.append(option)
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return res

# python
# LC 996 - Number of Squareful Arrays
# IDEA: permutations with duplicates (sort + same-level skip) + prune on the adjacent pair
# time = O(n!) worst case, far less after pruning, space = O(n)
import math

def numSquarefulPerms(nums):
    nums = sorted(nums)                  # equal values adjacent: the skip needs it
    n = len(nums)
    used = [False] * n
    path = []
    count = 0

    def is_square(x):
        root = math.isqrt(x)             # integer square root: no float rounding
        return root * root == x

    def backtrack():
        nonlocal count
        if len(path) == n:
            count += 1
            return
        for i in range(n):
            if used[i]:
                continue
            # same value as the left neighbour, which is not on the path: same level, skip
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue
            # the new neighbour pair must sum to a square
            if path and not is_square(path[-1] + nums[i]):
                continue
            used[i] = True
            path.append(nums[i])
            backtrack()
            path.pop()
            used[i] = False

    backtrack()
    return count

# python
# LC 93 - Restore IP Addresses
# IDEA: cut s into 4 pieces; each piece is 1-3 digits, <= 255, no leading zero;
#       prune when the digits left cannot fill the pieces left (need k..3k digits for k pieces)
# time = O(3^4 * n), space = O(n)   at most 3 choices per piece, 4 pieces, O(n) to join
def restoreIpAddresses(s):
    res = []
    path = []

    def backtrack(start):
        if len(path) == 4:
            if start == len(s):          # every digit used
                res.append(".".join(path))
            return
        pieces_left = 4 - len(path)
        digits_left = len(s) - start
        if digits_left < pieces_left or digits_left > 3 * pieces_left:
            return                       # cannot finish: too few, or too many, digits left
        for end in range(start + 1, min(start + 3, len(s)) + 1):
            piece = s[start:end]
            if len(piece) > 1 and piece[0] == "0":
                break                    # "0x" is invalid, and so is every longer piece
            if int(piece) > 255:
                break                    # longer pieces are larger still
            path.append(piece)
            backtrack(end)
            path.pop()

    backtrack(0)
    return res

path              start  pieces_left  digits_left  action
[]                0      4            4            try "0" (len 1); "00" breaks on the leading zero
["0"]             1      3            3            try "0"
["0","0"]         2      2            2            try "0"
["0","0","0"]     3      1            1            try "0"
["0","0","0","0"] 4      -            -            4 pieces and start == len(s) -> record "0.0.0.0"

# python
# LC 140 - Word Break II
# IDEA: cut at every dictionary prefix; memoise the sentences of each suffix by its start index
# time = O(n^3) for the n x n slices of up to n chars, plus building every cached sentence
#        (exponential in n in the worst case); space = O(n^2) chars in memo even for one answer
#        ("a" * n with ["a"]: memo[i] holds a sentence of length ~2(n - i)), plus the output
def wordBreak(s, wordDict):
    words = set(wordDict)                # O(1) membership
    memo = {}                            # start -> every sentence that spells s[start:]

    def sentences_from(start):
        if start == len(s):
            return [""]                  # one way to spell the empty suffix
        if start in memo:
            return memo[start]
        sentences = []
        for end in range(start + 1, len(s) + 1):
            word = s[start:end]
            if word not in words:
                continue
            for rest in sentences_from(end):
                if rest:
                    sentences.append(word + " " + rest)
                else:
                    sentences.append(word)
        memo[start] = sentences
        return sentences

    return sentences_from(0)

# python
# LC 980 - Unique Paths III
# IDEA: grid backtrack from the start; count arrivals at the end that used every walkable cell
# time = O(3^(m*n)), space = O(m*n)   after the first step at most 3 unvisited directions
def uniquePathsIII(grid):
    rows, cols = len(grid), len(grid[0])
    walkable = 0                         # start + end + empty cells
    start_r = start_c = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != -1:
                walkable += 1
            if grid[r][c] == 1:
                start_r, start_c = r, c
    count = 0

    def dfs(r, c, remaining):            # remaining = walkable cells not yet on the path
        nonlocal count
        if grid[r][c] == 2:
            if remaining == 0:           # the end only counts once every cell is covered
                count += 1
            return
        saved = grid[r][c]
        grid[r][c] = -1                  # mark: an obstacle for the calls below
        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 grid[nr][nc] != -1:
                dfs(nr, nc, remaining - 1)
        grid[r][c] = saved               # restore after the last direction

    dfs(start_r, start_c, walkable - 1)  # the start cell is already on the path
    return count

# python
# LC 22 - Generate Parentheses
# IDEA: count the brackets placed; '(' while open < n, ')' while close < open
# time = O(4^n / sqrt(n)), space = O(n)   the n-th Catalan number of answers, O(n) each
def generateParenthesis(n):
    res = []
    path = []

    def backtrack(open_count, close_count):
        if len(path) == 2 * n:
            res.append("".join(path))
            return
        if open_count < n:               # an opener is still available
            path.append("(")
            backtrack(open_count + 1, close_count)
            path.pop()
        if close_count < open_count:     # a closer has something to match
            path.append(")")
            backtrack(open_count, close_count + 1)
            path.pop()

    backtrack(0, 0)
    return res

// java
// LC 22 - Generate Parentheses
// IDEA: count the brackets placed; '(' while open < n, ')' while close < open
// time = O(4^n / sqrt(n)), space = O(n)
public List<String> generateParenthesis(int n) {
    List<String> res = new ArrayList<>();
    build(n, 0, 0, new StringBuilder(), res);
    return res;
}

private void build(int n, int open, int close, StringBuilder path, List<String> res) {
    if (path.length() == 2 * n) {
        res.add(path.toString());
        return;
    }
    if (open < n) {                                   // an opener is still available
        path.append('(');
        build(n, open + 1, close, path, res);
        path.deleteCharAt(path.length() - 1);
    }
    if (close < open) {                               // a closer has something to match
        path.append(')');
        build(n, open, close + 1, path, res);
        path.deleteCharAt(path.length() - 1);
    }
}