Chương 3 - Recursion

Recursion (đệ quy) là ngôn ngữ tự nhiên để mô tả bài toán có cấu trúc tự tương tự - giải bài lớn bằng cách kết hợp lời giải của vài bài con nhỏ hơn. Chương này dạy bạn cảm nhận 3 thành phần của một lời giải đệ quy: (i) base case (điều kiện dừng), (ii) recursive case (gọi vào bài con nhỏ hơn), (iii) kết hợp kết quả từ các bài con. Khi 3 cái này “click”, bạn sẽ thấy DP, Backtracking, Tree, Graph DFS đều là cùng một ngôn ngữ.

Mục tiêu chương

Sau chương này, bạn sẽ:

  • Hiểu 3 thành phần đệ quy: base case, recursive case, kết hợp.
  • Phân biệt recursion / backtracking / DFS / top-down DP.
  • Thuộc mantra choose → explore → unchoose cho backtracking.
  • Nhận diện overlapping subproblems → biết khi thêm @cache.
  • Cảnh giác Python recursion limit (~1000) và bẫy RecursionError.

Khi nào dùng pattern này?

  • Đề bài mô tả cấu trúc đệ quy tự nhiên: cây, đồ thị, chia đôi, liệt kê tất cả khả năng.
  • Bài có thể phát biểu dưới dạng f(n) = ... f(n-1) ... hoặc f(L,R) = ... f(L,M) + f(M+1,R) ....
  • Bài đếm/liệt kê tổ hợp / hoán vị / tập con - recursion + backtracking.

3 câu hỏi cần trả lời trước khi code đệ quy: 1. Trạng thái của hàm gồm những biến gì? (Cần đủ để định nghĩa “bài con”.) 2. Base case là gì? (Khi nào trả về luôn?) 3. Bước đệ quy chia bài lớn thành bài con thế nào, kết hợp kết quả ra sao?

Template code 

from functools import cache

# 1) Đệ quy "thuần" (có thể chậm vì lặp lại bài con).
def recurse(state):
    if base_condition(state):
        return base_value
    result = combine(recurse(subproblem_1(state)),
                     recurse(subproblem_2(state)))
    return result


# 2) Top-down DP: thêm cache để O(số trạng thái).
@cache
def f(*state):
    if base_condition(*state):
        return base_value
    return combine(f(*sub1(*state)), f(*sub2(*state)))


# 3) Backtracking: liệt kê + undo.
def backtrack(path, choices):
    if is_solution(path):
        results.append(path.copy())
        return
    for c in choices:
        if not valid(c, path):
            continue
        path.append(c)
        backtrack(path, next_choices(choices, c))
        path.pop()              # undo - đặc trưng của backtracking

Bài tự luyện cuối chương

  • LC 21 - Merge Two Sorted Lists (đệ quy trên LL)
  • LC 24 - Swap Nodes in Pairs
  • LC 95 - Unique Binary Search Trees II
  • LC 96 - Unique Binary Search Trees (Catalan)
  • LC 247 - Strobogrammatic Number II
  • LC 779 - K-th Symbol in Grammar

3.1 Fibonacci số thứ n (LC 509)

Đề bài

Tính số Fibonacci thứ n theo định nghĩa: F(0) = 0, F(1) = 1, và F(n) = F(n-1) + F(n-2) với n >= 2.

Ví dụ 

Input:  n = 2  → 1
Input:  n = 3  → 2
Input:  n = 10 → 55

Ràng buộc

  • 0 <= n <= 30 (LC); follow-up thường mở lên n <= 10^6 hoặc n <= 10^18.

Clarifying questions

  • n có thể lớn cỡ nào? → Quyết định cách chọn: đệ quy thuần / DP / matrix expo.
  • Có cần modulo không? → Khi n lớn (10^18), thường modulo 10^9+7.

Hướng tiếp cận

Cách 1 - Đệ quy thuần, O(2^n). Mỗi F(n) gọi 2 lần đệ quy. Cây gọi có ~2^n node → rất chậm.

Cách 2 - Memoization (top-down DP), O(n) time, O(n) space. Cache lại kết quả → mỗi F(k) tính đúng 1 lần.

Cách 3 - Iterative (bottom-up), O(n) time, O(1) space. Chỉ cần 2 biến prev, curr cuộn từ dưới lên.

Cách 4 - Matrix exponentiation, O(log n). Khi n lên đến 10^18.

Hình minh hoạ - cây gọi đệ quy cho F(5):

                F(5)
              /      \
          F(4)        F(3)
         /    \      /    \
       F(3)  F(2) F(2)   F(1)
       /  \   / \  / \
     F(2) F(1)...   ...   ← F(3), F(2), F(1) bị tính LẠI nhiều lần

→ Nếu memo cache mỗi F(k), số subproblem chỉ là n+1 (n=5 → 6 calls).
→ Nếu không memo, số calls ~ Fibonacci(n+1) ~ φ^n (exponential).

Code Python 3 

from functools import cache

class Solution:
    """Cách 3 - iterative O(1) space, đáp án production."""
    def fib(self, n: int) -> int:
        if n < 2:
            return n
        prev, curr = 0, 1
        for _ in range(2, n + 1):
            prev, curr = curr, prev + curr
        return curr


class SolutionMemo:
    """Cách 2 - top-down DP."""
    @cache
    def fib(self, n: int) -> int:
        if n < 2:
            return n
        return self.fib(n - 1) + self.fib(n - 2)


class SolutionMatrix:
    """Cách 4 - Matrix exponentiation, O(log n)."""
    MOD = 10**9 + 7

    def fib(self, n: int) -> int:
        if n < 2:
            return n
        # [[F(n+1), F(n)], [F(n), F(n-1)]] = [[1,1],[1,0]] ^ n
        result, base = [[1, 0], [0, 1]], [[1, 1], [1, 0]]
        while n > 0:
            if n & 1:
                result = self._mul(result, base)
            base = self._mul(base, base)
            n >>= 1
        return result[0][1]  # F(n)

    def _mul(self, a, b):
        return [[(a[0][0]*b[0][0] + a[0][1]*b[1][0]) % self.MOD,
                 (a[0][0]*b[0][1] + a[0][1]*b[1][1]) % self.MOD],
                [(a[1][0]*b[0][0] + a[1][1]*b[1][0]) % self.MOD,
                 (a[1][0]*b[0][1] + a[1][1]*b[1][1]) % self.MOD]]

Phân tích độ phức tạp

  • Iterative: O(n) time, O(1) space - best cho mọi case thường.
  • Top-down memo: O(n) time, O(n) space (stack + cache).
  • Matrix expo: O(log n) time - khi n cực lớn.

Bình luận

  • Bài học cốt lõi: Fibonacci là “hello world” của Dynamic Programming. Cả 3 từ khoá DP đều xuất hiện ở đây: overlapping subproblems, optimal substructure, state reduction.
  • Bẫy thường gặp:
    • Đệ quy không memo → exponential time, sẽ TLE ngay từ n >= 40.
    • Quên base case n < 2 → vô hạn đệ quy.
  • Follow-up phổ biến:
    1. LC 70 - Climbing Stairs: y hệt Fibonacci nhưng F(0) = F(1) = 1.
    2. LC 746 - Min Cost Climbing Stairs.
    3. LC 1137 - N-th Tribonacci.

Bài tự luyện liên quan

  • LC 70 - Climbing Stairs.
  • LC 1137 - N-th Tribonacci Number.
  • LC 198 - House Robber (cũng dùng pattern 2 biến).

3.2 Power(x, n) (LC 50)

Đề bài

Cài đặt hàm tính x^n với x là số thực và n là số nguyên (có thể âm).

Ví dụ 

Input:  x = 2.00000, n = 10     → 1024.00000
Input:  x = 2.10000, n = 3      → 9.26100
Input:  x = 2.00000, n = -2     → 0.25

Ràng buộc

  • -100.0 < x < 100.0
  • -2^31 <= n <= 2^31 - 1
  • Kết quả phải fit trong double precision.

Clarifying questions

  • Khi n âm, kết quả là 1 / x^|n|? → Đúng.
  • x = 0 và n = 0? → Quy ước 0^0 = 1 (theo LC).
  • Có cần ổn định số học (numerical stability) không? → Mặc định LC chấp nhận sai số nhỏ.

Hướng tiếp cận

Cách 1 - Nhân tay, O(n). Loop nhân n lần. TLE khi n = 2^31.

Cách 2 - Fast Power (đệ quy / iterative), O(log n).

Quan sát đệ quy: - Nếu n == 0: trả 1. - Nếu n chẵn: x^n = (x^(n/2))^2. - Nếu n lẻ: x^n = x · x^(n-1).

Cho phép n âm: gọi đệ quy với n = -n rồi nghịch đảo.

Hình minh hoạ - cây gọi cho x^10:

                  x^10
                   │ chẵn → (x^5)^2
                   ▼
                  x^5
                   │ lẻ → x · x^4
                   ▼
                  x^4
                   │ chẵn → (x^2)^2
                   ▼
                  x^2
                   │ chẵn → (x^1)^2
                   ▼
                  x^1
                   │ lẻ → x · x^0
                   ▼
                  x^0 = 1

Tổng số phép nhân: ~ 2 log₂(10) ≈ 8  (vs. 10 phép của brute force)

Code Python 3 

class Solution:
    """Đệ quy fast power."""

    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1.0
        if n < 0:
            return 1.0 / self.myPow(x, -n)
        half = self.myPow(x, n // 2)
        return half * half if n % 2 == 0 else half * half * x


class SolutionIter:
    """Iterative - tránh chiều sâu đệ quy. Đọc bit từ thấp lên cao."""

    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x, n = 1.0 / x, -n
        result = 1.0
        base = x
        while n > 0:
            if n & 1:
                result *= base
            base *= base
            n >>= 1
        return result

Phân tích độ phức tạp

  • Thời gian: O(log n) - mỗi bước chia đôi.
  • Bộ nhớ: Đệ quy O(log n) (call stack); iterative O(1).

Bình luận

  • Bẫy thường gặp:
    • Trong nhiều ngôn ngữ, n = -2^31 khi đảo dấu thành 2^31 sẽ overflow. Python int vô hạn nên an toàn, nhưng vẫn nên ý thức.
    • Quên n // 2 (integer division) → tính sai khi n lẻ.
    • Không tách “half = …” mà gọi đệ quy 2 lần cho cùng tham số → mất tính O(log n).
  • Follow-up phổ biến:
    1. Modular fast power: x^n mod m - đổi *= thành * % m.
    2. Matrix exponentiation - áp dụng đúng ý tưởng này lên ma trận (xem 3.1).
    3. Bài LC 372 - Super Pow: n cực lớn, biểu diễn dạng mảng chữ số.

Bài tự luyện liên quan

  • LC 372 - Super Pow.
  • LC 29 - Divide Two Integers (cùng tinh thần chia đôi).
  • LC 233 - Number of Digit One.

3.3 Reverse Linked List (đệ quy) (LC 206)

Đề bài

Cho head của một danh sách liên kết đơn. Hãy đảo ngược danh sách và trả về node đầu mới. (Bài này có 2 cách: iterative và đệ quy. Ở chương này tập trung bản đệ quy; bản iterative gặp lại ở Chương 7.)

Ví dụ 

Input:  head = 1 → 2 → 3 → 4 → 5 → None  (singly linked list)
Output: 5 → 4 → 3 → 2 → 1 → None

Input:  head = None     (empty list)
Output: None

Ràng buộc

  • 0 <= số node <= 5000
  • -5000 <= node.val <= 5000

Clarifying questions

  • Có cho phép sửa node (sửa .next) không? → Có, đó là yêu cầu chính.
  • Linked list có vòng không? → Theo đề: không.

Hướng tiếp cận

Ý tưởng đệ quy: - Base case: nếu head là None hoặc head.next là None → trả head. - Đệ quy: gọi reverseList(head.next) để đảo phần đuôi, được node cuối mới (chính là node cuối cũ → đầu mới sau khi đảo). - Kết hợp: lúc này head.next vẫn trỏ tới node cũ ngay sau head (chưa bị thay đổi vì đệ quy chỉ làm với phần đuôi). Ta gán head.next.next = head và head.next = None để khâu head vào cuối danh sách đã đảo.

Hình minh hoạ với 1 → 2 → 3 → None:

Gọi reverseList(1):
  reverseList(2):
    reverseList(3):
      base case → return 3            #  3 → None
    # tại đây head=2, head.next=3
    # phần đuôi đã đảo: 3 → None
    # ta cần khâu 2 vào sau 3:
    head.next.next = head              #  3 → 2
    head.next = None                   #  2 → None
    # giờ chuỗi: 3 → 2 → None, đầu mới = 3
    return 3
  # tại đây head=1, head.next=2
  # phần đuôi đã đảo: 3 → 2 → None
  # khâu 1 vào sau 2:
  head.next.next = head                #  2 → 1
  head.next = None                     #  1 → None
  # giờ chuỗi: 3 → 2 → 1 → None
  return 3

Code Python 3 

class ListNode:
    def __init__(self, val: int = 0, next: 'ListNode | None' = None):
        self.val = val
        self.next = next


class Solution:
    def reverseList(self, head: ListNode | None) -> ListNode | None:
        if head is None or head.next is None:
            return head
        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return new_head

Phân tích độ phức tạp

  • Thời gian: O(n) - mỗi node được duyệt đúng 1 lần.
  • Bộ nhớ: O(n) cho call stack (vì đệ quy không tail-call optimized trong Python).

Bình luận

  • Bẫy thường gặp:
    • Quên gán head.next = None → vòng lặp vô hạn (1 → 2 → 1 → 2 …).
    • Trả về head thay vì new_head → mất phần đuôi.
    • Code thử trên bài có vài chục nghìn node → Python RecursionError. Khi đó chuyển sang iterative (xem code dưới):
prev = None
while head:
    nxt = head.next
    head.next = prev
    prev = head
    head = nxt
return prev
  • Follow-up phổ biến:
    1. LC 92 - Reverse Linked List II: đảo trong khoảng [left, right].
    2. LC 25 - Reverse Nodes in k-Group (Chương 7).
    3. LC 234 - Palindrome Linked List: dùng đảo nửa sau.

Bài tự luyện liên quan

  • LC 92 - Reverse Linked List II.
  • LC 234 - Palindrome Linked List.
  • LC 24 - Swap Nodes in Pairs.

3.4 Generate Parentheses (LC 22)

Đề bài

Cho số nguyên n, sinh tất cả các chuỗi dấu ngoặc đúng (well-formed) độ dài 2n.

Ví dụ 

Input:  n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]

Input:  n = 1
Output: ["()"]

Ràng buộc

  • 1 <= n <= 8

Clarifying questions

  • Output có cần sort không? → Không, miễn đúng và đủ.
  • Đếm số bằng cách đệ quy đủ không? → Đếm thuần là số Catalan C(n) = (2n)! / (n!(n+1)!). Nhưng bài này yêu cầu liệt kê.

Hướng tiếp cận

Ý tưởng: Sinh ký tự ( hoặc ) từng bước. Mỗi bước có 2 lựa chọn, nhưng phải đảm bảo tính hợp lệ: - Số ( đã đặt không vượt quá n. - Số ) đã đặt không vượt quá số ( đã đặt (vì sẽ tạo ngoặc không match).

Đệ quy với 2 counter: open_count, close_count. Khi len(path) == 2n → đẩy vào kết quả.

Hình minh hoạ - cây quyết định cho n = 2:

                       ""
                     /    \
                ( /        \ )  ✗ (close > open)
                   "("
                  /   \
              ( /      \ )
              "(("    "()"
               │        │
            ) ▼     ( / \ )  ✗
              "(()"   "()("
               │       │
            ) ▼     ) ▼
              "(())" ★  "()()" ★

Đáp án: ["(())", "()()"]
(✗ = nhánh bị cắt vì không hợp lệ)

Code Python 3 

from typing import List

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result: list[str] = []

        def backtrack(path: list[str], open_cnt: int, close_cnt: int) -> None:
            if len(path) == 2 * n:
                result.append(''.join(path))
                return
            if open_cnt < n:
                path.append('(')
                backtrack(path, open_cnt + 1, close_cnt)
                path.pop()
            if close_cnt < open_cnt:
                path.append(')')
                backtrack(path, open_cnt, close_cnt + 1)
                path.pop()

        backtrack([], 0, 0)
        return result

Phân tích độ phức tạp

  • Thời gian: O(C(n) · n) với C(n) = số Catalan thứ n = (2n)! / (n!(n+1)!). Mỗi chuỗi tốn O(n) để build.
  • Bộ nhớ: O(n) cho call stack + O(C(n) · n) cho output.

Bình luận

  • Bẫy thường gặp:
    • Cho phép thêm ) khi close_cnt >= open_cnt → sinh ra chuỗi sai như ())).
    • Quên path.pop() sau đệ quy → state dirty cho nhánh kế.
  • Hai điều kiện cắt nhánh là cốt lõi của Backtracking:
    • Trước khi đặt phần tử → kiểm tra valid (không cần undo nếu skip).
    • Sau khi đặt → đệ quy + undo ngay sau khi quay về.
  • Follow-up phổ biến:
    1. LC 20 - Valid Parentheses: chỉ kiểm tra hợp lệ (Chương 8).
    2. LC 32 - Longest Valid Parentheses: tìm dãy con dài nhất hợp lệ (DP / stack).
    3. LC 301 - Remove Invalid Parentheses.

Bài tự luyện liên quan

  • LC 20 - Valid Parentheses.
  • LC 17 - Letter Combinations of a Phone Number.
  • LC 39 - Combination Sum.

3.5 Permutations (LC 46)

Đề bài

Cho mảng nums các số phân biệt, trả về tất cả hoán vị có thể của chúng.

Ví dụ 

Input:  nums = [1, 2, 3]
Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Ràng buộc

  • 1 <= len(nums) <= 6
  • -10 <= nums[i] <= 10
  • Tất cả số trong nums phân biệt.

Clarifying questions

  • Có duplicate không? → Theo đề: không (LC 47 mới có duplicate).
  • Output cần sort không? → Không.

Hướng tiếp cận

Ý tưởng: Tại mỗi bước, chọn 1 số chưa dùng đẩy vào path. Khi path đủ n phần tử → 1 hoán vị hoàn chỉnh.

2 cách quản lý “đã dùng”: - Mảng used: bool[n]. - Hoặc dùng set các index đã dùng.

Hình minh hoạ - cây quyết định cho [1, 2, 3]:

                          [ ]
              ┌────────────┼────────────┐
            [1]           [2]          [3]
           /   \         /   \         /  \
        [1,2] [1,3]   [2,1] [2,3]   [3,1] [3,2]
          │     │       │     │       │     │
       [1,2,3][1,3,2] [2,1,3][2,3,1][3,1,2][3,2,1]

Tổng: 3 · 2 · 1 = 6 hoán vị.

Code Python 3 

from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result: list[list[int]] = []
        n = len(nums)
        used = [False] * n
        path: list[int] = []

        def backtrack() -> None:
            if len(path) == n:
                result.append(path.copy())
                return
            for i in range(n):
                if used[i]:
                    continue
                used[i] = True
                path.append(nums[i])
                backtrack()
                path.pop()
                used[i] = False

        backtrack()
        return result


class SolutionSwap:
    """Cách 2 - swap in-place, không cần mảng used."""

    def permute(self, nums: List[int]) -> List[List[int]]:
        result: list[list[int]] = []

        def backtrack(start: int) -> None:
            if start == len(nums):
                result.append(nums.copy())
                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

        backtrack(0)
        return result

Phân tích độ phức tạp

  • Thời gian: O(n · n!) - có n! hoán vị, mỗi cái build trong O(n).
  • Bộ nhớ: O(n) cho call stack + path (không tính output).

Bình luận

  • Bẫy thường gặp:
    • Quên path.copy() → mọi entry trong result trỏ tới cùng list (bị thay đổi sau).
    • Quên used[i] = False khi undo → bỏ sót hoán vị.
  • Follow-up phổ biến:
    1. LC 47 - Permutations II: có duplicate. Phải sort trước và skip duplicate trong cùng level: if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue.
    2. LC 60 - Permutation Sequence: tìm hoán vị thứ k mà không liệt kê tất cả.
    3. LC 31 - Next Permutation: cũng dùng “swap
      • reverse” pattern.
  • Liên hệ: Đây là template chuẩn cho backtracking. Cùng pattern xuất hiện ở Combinations, Subsets, N-Queens, Sudoku.

Bài tự luyện liên quan

  • LC 47 - Permutations II (duplicate).
  • LC 60 - Permutation Sequence.
  • LC 31 - Next Permutation.

3.6 Subsets (LC 78)

Đề bài

Cho mảng nums các số phân biệt. Trả về tất cả tập con có thể của nums (bao gồm tập rỗng và tập đầy đủ). Tổng cộng 2^n tập con.

Ví dụ 

Input:  nums = [1, 2, 3]
Output: [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

Input:  nums = [0]
Output: [[], [0]]

Ràng buộc

  • 1 <= len(nums) <= 10
  • -10 <= nums[i] <= 10
  • Tất cả số phân biệt.

Clarifying questions

  • Output có cần sort không? → Không.
  • Có duplicate không? → Không (LC 90 mới có).

Hướng tiếp cận

Có 3 cách kinh điển, đều nên biết.

Cách 1 - Backtracking “chọn / không chọn”. Tại mỗi index i, có 2 nhánh: thêm nums[i] vào path hoặc bỏ qua.

Cách 2 - Backtracking “bắt đầu từ start”. Mỗi node trong cây gọi result.append(path.copy()) (mọi prefix đều là tập con hợp lệ), rồi loop for i in range(start, n).

Cách 3 - Bit Mask iteration. Mỗi số từ 0 đến 2^n - 1 đại diện cho 1 tập con: bit i bật ↔︎ nums[i] trong tập. (Xem thêm Chương 21.)

Hình minh hoạ - cây “chọn / không chọn” cho [1, 2, 3]:

                            [ ]
                bỏ 1 /          \ chọn 1
                  [ ]             [1]
            bỏ 2 / \ chọn 2     bỏ 2 / \ chọn 2
                [ ] [2]            [1] [1,2]
          bỏ3/\ ... ...          ...  ...
           [ ] [3]

Mỗi LÁ của cây = 1 tập con. Cây có 2^3 = 8 lá.

Code Python 3 

from typing import List

class Solution:
    """Cách 2 - gom mọi prefix là 1 tập con."""

    def subsets(self, nums: List[int]) -> List[List[int]]:
        result: list[list[int]] = []
        path: list[int] = []

        def backtrack(start: int) -> None:
            result.append(path.copy())          # mọi state đều là một subset
            for i in range(start, len(nums)):
                path.append(nums[i])
                backtrack(i + 1)
                path.pop()

        backtrack(0)
        return result


class SolutionBitmask:
    """Cách 3 - iterate qua 2^n bitmask."""

    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        result = []
        for mask in range(1 << n):
            subset = [nums[i] for i in range(n) if mask & (1 << i)]
            result.append(subset)
        return result


class SolutionPick:
    """Cách 1 - backtracking chọn / không chọn."""

    def subsets(self, nums: List[int]) -> List[List[int]]:
        result: list[list[int]] = []
        path: list[int] = []

        def backtrack(i: int) -> None:
            if i == len(nums):
                result.append(path.copy())
                return
            # nhánh không chọn nums[i]
            backtrack(i + 1)
            # nhánh chọn nums[i]
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

        backtrack(0)
        return result

Phân tích độ phức tạp

  • Thời gian: O(n · 2^n) - có 2^n tập con, mỗi cái copy trong O(n).
  • Bộ nhớ: O(n) cho call stack (không tính output).

Bình luận

  • Bẫy thường gặp:
    • Quên path.copy() trong result.append(path)
      • tất cả entry sẽ là tham chiếu tới cùng list.
    • Trong cách 2: nhớ result.append(path.copy()) trước khi loop (mọi prefix là tập con); nếu để sau loop sẽ thiếu các tập con “lá”.
  • Follow-up phổ biến:
    1. LC 90 - Subsets II: có duplicate. Sort + skip if i > start and nums[i] == nums[i-1]: continue.
    2. LC 78 vs LC 77 (Combinations): cùng template, chỉ khác điều kiện append (Combinations chỉ append khi len(path) == k).
    3. LC 698 - Partition to K Equal Sum Subsets (bài Bitmask DP, Chương 40).
  • Liên kết toàn cục: Hiểu rõ “chọn / không chọn” sẽ giúp bạn intuition cho mọi bài knapsack ở Chương 29.

Bài tự luyện liên quan

  • LC 90 - Subsets II.
  • LC 77 - Combinations.
  • LC 39 - Combination Sum.

Tóm tắt chương & Quyết định

Recursion vs DFS vs Backtracking vs Top-down DP

Thuộc tính Recursion DFS Backtracking Top-down DP
Mục tiêu Giải bài con tự gọi lại Duyệt graph/tree Liệt kê tất cả lời giải Giải tối ưu / đếm
Có undo state? Không bắt buộc Hiếm Bắt buộc (choose/unchoose) Không
Có memo? Có thể có Hiếm Hiếm (state phụ thuộc đường đi) Bắt buộc
Ví dụ Factorial, Fibonacci Number of Islands Permutations, N-Queens LCS, Coin Change

Mantra backtracking 

def backtrack(path, choices):
    if is_goal(path):
        record(path); return
    for c in choices:
        if not feasible(path, c): continue
        path.append(c)          # choose
        backtrack(path, ...)    # explore
        path.pop()              # unchoose

Python recursion caveats

  • Default limit 1000; cây/list dài >1000 → sys.setrecursionlimit(10**6) và tăng stack (threading.stack_size).
  • Không có tail-call optimization. def f(n): return f(n-1) vẫn stack overflow.
  • Recursion sâu trong hot loop chậm hơn iterative ~3–5×.