1.1 Backtracking là gì?

Cây quyết định cho Permutations của [1,2,3] — mỗi nhánh là một lựa chọn, đệ quy đến lá

Backtracking khác DFS thường ở chỗ "undo" — sau khi thử nhánh trái, khôi phục trạng thái rồi thử nhánh phải.

1.2 Template chuẩn — Choose / Recurse / Unchoose

def backtrack(state, path):
    if is_solution(state):
        result.append(path[:])           # COPY path
        return
    for choice in get_choices(state):
        if not is_valid(choice, state):
            continue                     # PRUNING
        # CHOOSE
        path.append(choice)
        update_state(state, choice)
        # RECURSE
        backtrack(state, path)
        # UNCHOOSE — KHÔI PHỤC
        path.pop()
        revert_state(state, choice)

Bốn yếu tố then chốt

1. State — biểu diễn "trạng thái hiện tại" (path đã chọn, used set, board state).
2. Solution check — khi nào dừng và lưu kết quả.
3. Choices — các lựa chọn khả dĩ tại bước hiện tại.
4. Undo — phải khôi phục đầy đủ sau đệ quy.

1.3 Tín hiệu nhận biết Backtracking

Quy tắc constraint → algorithm

• n ≤ 10 → có thể O(n!) — permutations.
• n ≤ 20 → O(2ⁿ) — subsets.
• n ≤ 100 → cần O(n²) hoặc tốt hơn (DP).

Khi đề có constraint nhỏ bất thường → đó là dấu hiệu cho phép thuật toán chậm.

1.4 Time complexity của Backtracking

Backtracking là DFS trên cây quyết định. Time complexity = (số node) × (chi phí mỗi node).

Yếu tố "n × ..." trong time là chi phí copy path khi tìm thấy solution. Nếu chỉ đếm (không liệt kê), có thể giảm xuống.

2.1 Subsets — Pattern

Hai cách tiếp cận chính

1. "Include or Exclude": tại mỗi vị trí, chọn lấy hoặc không lấy.
2. "Pick at index i": từ vị trí start, chọn 1 phần tử rồi đệ quy với start mới.

Khoá học khuyến nghị approach 2 — tổng quát hơn (dùng cho Combinations, Combination Sum).

def subsets(nums):
    res = []
    def backtrack(start, path):
        res.append(path[:])              # subset hiện tại là 1 nghiệm
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)        # i+1 để không lấy lại
            path.pop()
    backtrack(0, [])
    return res

2.2 Worked Example 1 — Subsets (#78) — Trace

nums = [1, 2, 3]. Kỳ vọng 8 subsets.

Kết quả: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]. Time O(n × 2ⁿ).

2.3 Worked Example 2 — Subsets II (with duplicates)

Đề (LeetCode #90): Như #78 nhưng nums có thể trùng. Không cho phép subset trùng.

Ví dụ: [1, 2, 2] → [[], [1], [1,2], [1,2,2], [2], [2,2]].

Mẹo: Sort + skip duplicate ở cùng level

def subsetsWithDup(nums):
    nums.sort()                         # quan trọng — đẩy duplicate cạnh nhau
    res = []
    def backtrack(start, path):
        res.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]:
                continue                # skip duplicate Ở CÙNG level
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return res

2.4 Permutations — Pattern

Khác Subsets ở chỗ nào?

Permutations quan tâm thứ tự: [1,2] và [2,1] là 2 nghiệm khác nhau. Subsets thì không.

Hệ quả: tại mỗi bước, được chọn từ mọi phần tử chưa dùng, không chỉ phần tử sau index hiện tại.

def permute(nums):
    res = []
    def backtrack(path, used):
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]: continue
            used[i] = True
            path.append(nums[i])
            backtrack(path, used)
            path.pop()
            used[i] = False             # UNCHOOSE
    backtrack([], [False] * len(nums))
    return res

Time O(n × n!).

2.5 Worked Example 3 — Permutations (#46)

Đã có code ở 2.4. Dưới đây là biến thể không cần used array, dùng swap in-place:

def permute(nums):
    res = []
    def backtrack(start):
        if start == len(nums):
            res.append(nums[:])
            return
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]    # undo swap
    backtrack(0)
    return res

Tiết kiệm space O(n) cho used array. Idiom kinh điển khi viết permutations.

So sánh hai approach

Trong phỏng vấn, dùng "used array" — rõ ràng hơn. Swap là tối ưu khi cần.

2.6 Worked Example 4 — Permutations II (with duplicates)

Đề (LeetCode #47): Như #46 nhưng nums có duplicate. Không cho phép permutation trùng.

Ví dụ: [1, 1, 2] → [[1,1,2], [1,2,1], [2,1,1]] (3 thay vì 6).

def permuteUnique(nums):
    nums.sort()
    res = []
    used = [False] * len(nums)
    def backtrack(path):
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]: continue
            # Skip duplicate ở cùng level KHI phần tử trước cùng giá trị CHƯA dùng
            if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack(path)
            path.pop()
            used[i] = False
    backtrack([])
    return res

2.7 Combinations — Pattern

Code (cùng pattern Subsets nhưng dừng khi đủ k)

def combine(n, k):
    res = []
    def backtrack(start, path):
        if len(path) == k:
            res.append(path[:])
            return
        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()
    backtrack(1, [])
    return res

Pruning quan trọng

Có thể prune khi "không còn đủ phần tử để hoàn thành":

# Số phần tử còn lại = (n - i + 1); cần thêm = (k - len(path))
# Nếu n - i + 1 < k - len(path) → impossible → break
for i in range(start, n - (k - len(path)) + 2):

Pruning này có thể giảm time đáng kể với k nhỏ và n lớn.

2.8 Worked Example 5 — Combinations (#77)

Đề: Trả mọi tổ hợp C(n, k) từ [1..n].

Đã có code ở 2.7. Trace với n=4, k=2:

Kết quả: 6 combinations. C(4,2) = 6 ✓.

2.9 Worked Example 6 — Combination Sum (#39)

Đề: Mảng candidates phân biệt, mỗi phần tử có thể dùng nhiều lần. Tìm mọi tổ hợp có tổng = target.

def combinationSum(candidates, target):
    res = []
    candidates.sort()                         # cho phép early break
    def backtrack(start, path, remain):
        if remain == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remain:
                break                          # PRUNING: sort + break
            path.append(candidates[i])
            backtrack(i, path, remain - candidates[i])    # i (không phải i+1) — cho phép dùng lại
            path.pop()
    backtrack(0, [], target)
    return res

Hai chi tiết then chốt

• backtrack(i, ...) chứ không phải i + 1: phần tử dùng được nhiều lần.
• break khi candidates[i] > remain: vì sort tăng dần, các phần tử sau cũng lớn hơn → vô ích tiếp tục.

Knowledge Check — Subsets / Permutations / Combinations

3.1 Pattern Grid Backtracking

Khác Grid BFS/DFS (Tuần 10) ở chỗ: cần "undo" mark visited để có thể dùng lại ô ở đường đi khác.

def has_path(grid, word):
    m, n = len(grid), len(grid[0])
    def dfs(r, c, idx):
        if idx == len(word): return True
        if r < 0 or r >= m or c < 0 or c >= n: return False
        if grid[r][c] != word[idx]: return False
        # CHOOSE
        original = grid[r][c]
        grid[r][c] = '#'                  # mark visited
        # RECURSE 4 directions
        found = (dfs(r+1, c, idx+1) or dfs(r-1, c, idx+1)
                 or dfs(r, c+1, idx+1) or dfs(r, c-1, idx+1))
        # UNCHOOSE
        grid[r][c] = original
        return found
    for r in range(m):
        for c in range(n):
            if dfs(r, c, 0): return True
    return False

Đây là tinh thần Number of Islands (Tuần 10) cộng thêm undo mark.

3.2 Worked Example 7 — Word Search (#79)

Đề: Lưới ký tự + word. Trả True nếu word có thể tạo bằng đường đi liên tiếp 4 hướng (không lặp ô).

Code ở 3.1 chính là lời giải. Phân tích:

Pruning hiệu quả

• Check sớm: grid[r][c] != word[idx] dừng nhánh ngay khi ký tự không khớp.
• Boundary check: dừng khi out-of-bounds.
• Visited mark: dùng '#' thay set — tiết kiệm O(L) bộ nhớ.

Time complexity

Worst case O(m × n × 4^L) với L = len(word). Mỗi ô khởi đầu, mỗi bước có 4 hướng và đi L bước.

Thực tế nhanh hơn nhiều nhờ pruning (đa số nhánh dừng sớm khi ký tự không khớp).

4.1 N-Queens — Pattern và Visualisation

Đề (LeetCode #51): Đặt n quân hậu trên bàn n×n sao cho không có 2 quân nào tấn công nhau (không cùng hàng/cột/đường chéo).

Một nghiệm 4-Queens: hậu ở (0,1), (1,3), (2,0), (3,2)

Quan sát

Đặt từng hàng một (vì mỗi hàng chỉ có 1 hậu). Tại hàng r, thử mỗi cột c: kiểm tra không xung đột với các hậu đã đặt → đệ quy hàng r+1.

4.2 Worked Example 8 — N-Queens (3-set Technique)

Để check xung đột O(1), dùng 3 set:

• cols: cột đã chiếm.
• diag1: đường chéo "/" (giá trị r + c cùng).
• diag2: đường chéo "\" (giá trị r - c cùng).

def solveNQueens(n):
    res = []
    cols = set(); d1 = set(); d2 = set()
    queens = [-1] * n                    # queens[r] = c
    def backtrack(r):
        if r == n:
            board = ['.'*c + 'Q' + '.'*(n-c-1) for c in queens]
            res.append(board)
            return
        for c in range(n):
            if c in cols or (r+c) in d1 or (r-c) in d2:
                continue                  # PRUNING — xung đột
            cols.add(c); d1.add(r+c); d2.add(r-c)
            queens[r] = c
            backtrack(r + 1)
            cols.discard(c); d1.discard(r+c); d2.discard(r-c)
    backtrack(0)
    return res

Time O(n!) với pruning mạnh. n = 8 → ~92 nghiệm; chạy < 100 ms.

4.3 N-Queens — Phân tích complexity

Worst case không pruning: n^n (mỗi hàng thử n cột). Với pruning bằng 3 set:

• Hàng 0: thử n cột → tốt cả n nhánh.
• Hàng 1: với mỗi cột của hàng 0, ~(n-3) cột hợp lệ.
• Hàng 2: ít hơn nữa…

Tổng số node được thăm thực tế xấp xỉ O(n!) — còn rất nhiều so với n^n.

Vai trò của pruning

Không pruning, n=8 sẽ là 8^8 ≈ 16 triệu nhánh. Có pruning, chỉ ~2,000 nhánh được thăm. Đây là minh chứng pruning quyết định tất cả.

4.4 Worked Example 9 — Sudoku Solver (#37)

Đề: Hoàn thành lưới Sudoku 9×9 hợp lệ. Mỗi hàng/cột/khối 3×3 chứa các chữ số 1-9 không trùng.

def solveSudoku(board):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    empties = []
    for r in range(9):
        for c in range(9):
            if board[r][c] == '.':
                empties.append((r, c))
            else:
                d = board[r][c]
                rows[r].add(d); cols[c].add(d); boxes[(r//3)*3 + c//3].add(d)

    def backtrack(idx):
        if idx == len(empties): return True
        r, c = empties[idx]
        b = (r//3)*3 + c//3
        for d in '123456789':
            if d in rows[r] or d in cols[c] or d in boxes[b]:
                continue
            rows[r].add(d); cols[c].add(d); boxes[b].add(d)
            board[r][c] = d
            if backtrack(idx + 1): return True
            rows[r].discard(d); cols[c].discard(d); boxes[b].discard(d)
            board[r][c] = '.'
        return False

    backtrack(0)

Time worst case mũ; pruning thực tế giải < 1s.

Knowledge Check — Constraint Satisfaction

5.1 Worked Example 10 — Palindrome Partitioning

Đề (LeetCode #131): Cho string s. Phân chia thành các substring sao cho mỗi substring là palindrome. Trả về mọi cách phân chia.

Ví dụ: "aab" → [["a","a","b"], ["aa","b"]].

def partition(s):
    res = []
    def is_pal(l, r):
        while l < r:
            if s[l] != s[r]: return False
            l += 1; r -= 1
        return True
    def backtrack(start, path):
        if start == len(s):
            res.append(path[:])
            return
        for end in range(start, len(s)):
            if is_pal(start, end):
                path.append(s[start:end+1])
                backtrack(end + 1, path)
                path.pop()
    backtrack(0, [])
    return res

Time O(n × 2ⁿ) worst case (mọi cách phân + check palindrome).

5.2 Sáu kỹ thuật pruning tổng quát

1. Sort + early break: sort input, trong vòng for break khi thấy giá trị quá lớn không còn khả thi (Combination Sum, Permutations II).
2. Bounds check: kiểm tra số lượng còn lại đủ để hoàn thành (Combinations với pruning n - i + 1 ≥ k - len(path)).
3. Constraint propagation: tính toán constraint ngay khi gán → rút bớt domain (3-set N-Queens, rows/cols/boxes Sudoku).
4. Skip duplicate at same level: if i > start and nums[i] == nums[i-1]: continue — tránh đếm trùng.
5. Memoisation: nếu cùng state xuất hiện nhiều lần → cache. Đây là cầu nối sang DP (Tuần 12).
6. Iterative deepening: bắt đầu với depth giới hạn, tăng dần. Hiệu quả khi nghiệm thường ở depth nhỏ.

Khi nào nghĩ đến memoisation?

Khi backtracking thử cùng (start, remaining) qua nhiều đường khác nhau. Đó là dấu hiệu chuyển sang DP — chủ đề chính của Tuần 12.

Knowledge Check — Pattern Reuse

6.0 Decision Tree — Backtracking

Quy trình code bài backtracking

1. Vẽ cây quyết định trên giấy với input nhỏ.
2. Xác định state, choices, solution check.
3. Viết template choose-recurse-unchoose.
4. Thêm pruning từ dễ đến khó.
5. Test trên duplicate input nếu có.

Tổng kết Tuần 11

Đã học

• Template chuẩn: choose — recurse — unchoose; quy tắc vàng append phải có pop.
• Subsets / Permutations / Combinations: ba bài kinh điển; biến thể duplicates với "skip ở cùng level".
• Combination Sum: backtrack(i, ...) cho phép dùng lại; sort + early break để prune.
• Grid Backtracking: Word Search với undo mark — khác Number of Islands.
• N-Queens: 3-set technique cho check xung đột O(1).
• Sudoku Solver: rows/cols/boxes constraint propagation.
• Palindrome Partitioning: partition pattern với backtrack(start, ...), end loop.
• Pruning: 6 kỹ thuật tổng quát; pruning quyết định bài chạy được hay TLE.

Bài về nhà (12 bài)

1. LeetCode #78 — Subsets
2. LeetCode #90 — Subsets II (duplicates)
3. LeetCode #46 — Permutations
4. LeetCode #47 — Permutations II (duplicates)
5. LeetCode #77 — Combinations
6. LeetCode #39 — Combination Sum
7. LeetCode #40 — Combination Sum II (duplicates)
8. LeetCode #79 — Word Search
9. LeetCode #51 — N-Queens (Hard)
10. LeetCode #37 — Sudoku Solver (Hard)
11. LeetCode #131 — Palindrome Partitioning
12. LeetCode #93 — Restore IP Addresses