Chương 28 - Backtracking

Backtracking = DFS đi kèm với undo state khi quay lui. Đây là pattern để liệt kê mọi cấu hình hợp lệ (permutation, subset, combination, Sudoku, N-Queens). Bí mật của backtracking hiệu quả là pruning - cắt nhánh sớm khi biết chắc không dẫn đến nghiệm.

Chương 12 bài - đầy đủ template + 12 bài kinh điển từ Medium đến Hard.

Mục tiêu chương

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

• Thuộc mantra choose → explore → unchoose.
• Skip duplicate ở mỗi level (sort + if i > start and ...).
• Pruning sớm: giới hạn start, check ngân sách (remaining count).
• Phân biệt: liệt kê tất cả vs đếm số cấu hình (chuyển sang DP).

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

• Cần liệt kê tất cả nghiệm (không chỉ đếm).
• Bài có cấu trúc đệ quy + lựa chọn nhiều nhánh tại mỗi bước.
• Không có optimal substructure → DP không áp dụng → backtracking + pruning.

3 thành phần của backtracking: 1. Choice: tại mỗi bước có lựa chọn nào? 2. Constraint: lựa chọn nào hợp lệ? 3. Goal: khi nào dừng và ghi kết quả?

Template code

def backtrack(path, choices):
    if is_goal(path):
        result.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 backtracking

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

• LC 78 - Subsets (Chương 3.6)
• LC 46 - Permutations (Chương 3.5)
• LC 22 - Generate Parentheses (Chương 3.4)
• LC 980 - Unique Paths III
• LC 1255 - Maximum Score Words

---

28.1 Combinations (LC 77)

Đề bài

Cho n và k. Trả về tất cả combination chọn k số từ 1..n.

Ví dụ

Input:  n = 4, k = 2
Output: [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]
        (thứ tự các combination trong output có thể tuỳ ý)

Ràng buộc

• 1 <= n <= 20
• 1 <= k <= n

Clarifying questions

• n = k? → Trả 1 combination duy nhất.
• k = 0? → Trả [[]] (empty combination).

Hướng tiếp cận

Backtracking với start: tại mỗi bước chọn 1 số ≥ start để tránh trùng.

def backtrack(start):
    if len(path) == k:
        result.append(path.copy()); return
    for i in range(start, n + 1):
        path.append(i)
        backtrack(i + 1)
        path.pop()

Code Python 3

from typing import List

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result: list[list[int]] = []
        path: list[int] = []

        def backtrack(start: int) -> None:
            if len(path) == k:
                result.append(path.copy())
                return
            # Pruning: cần thêm (k - len(path)) số, max start = n - (k - len(path)) + 1.
            for i in range(start, n - (k - len(path)) + 2):
                path.append(i)
                backtrack(i + 1)
                path.pop()

        backtrack(1)
        return result

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

• Thời gian: O(C(n, k) · k).
• Bộ nhớ: O(k) cho path + stack.

Bình luận

• Pruning quan trọng: giới hạn start để không phí nhánh không đủ số.

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

• LC 39 - Combination Sum (bài 28.5).
• LC 216 - Combination Sum III.

---

28.2 Subsets II (LC 90)

Đề bài

Cho nums (có thể duplicate). Trả về tất cả tập con không trùng.

Ví dụ

Input:  nums = [1, 2, 2]   (có duplicate)
Output: [[], [1], [1,2], [1,2,2], [2], [2,2]]
        (mọi subset duy nhất, mảng kết quả có thể theo thứ tự bất kỳ)

Ràng buộc

• 1 <= len(nums) <= 10
• -10 <= nums[i] <= 10

Clarifying questions

• nums rỗng? → Trả [[]].
• Tất cả trùng? → Sort + skip duplicate đảm bảo unique.

Hướng tiếp cận

Sort nums. Tại mỗi level, skip duplicate với if i > start and nums[i] == nums[i-1]: continue.

Code Python 3

from typing import List

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result: list[list[int]] = []
        path: list[int] = []

        def backtrack(start: int) -> None:
            result.append(path.copy())
            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i - 1]:
                    continue
                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).
• Bộ nhớ: O(n).

Bình luận

• Skip duplicate level same: i > start đảm bảo skip chỉ ở cùng level (cùng vòng for đệ quy), không skip giữa parent-child.

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

• LC 78 - Subsets.
• LC 47 - Permutations II (bài 28.3).

---

28.3 Permutations II (LC 47)

Đề bài

Cho nums có duplicate. Trả về tất cả hoán vị phân biệt.

Ví dụ

Input:  nums = [1, 1, 2]   (có duplicate)
Output: [[1,1,2], [1,2,1], [2,1,1]]
        (mọi permutation duy nhất)

Ràng buộc

• 1 <= len(nums) <= 8
• -10 <= nums[i] <= 10

Clarifying questions

• nums rỗng? → Trả [[]].
• Toàn số giống nhau? → Chỉ 1 hoán vị duy nhất.

Hướng tiếp cận

Sort + skip duplicate. Mảng used. Trick: nếu nums[i] == nums[i-1] và nums[i-1] chưa dùng → skip (đảm bảo dùng theo thứ tự index xuất hiện).

Code Python 3

from typing import List

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

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

        backtrack()
        return result

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

• Thời gian: O(n · n!).
• Bộ nhớ: O(n).

Bình luận

• Trick not used[i-1]: chỉ chọn cái cùng giá trị nếu cái trước đã chọn rồi.
• Equivalent: used[i-1] cũng OK - đảo logic.

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

• LC 46 - Permutations (Chương 3.5).
• LC 31 - Next Permutation.

---

28.4 Letter Combinations of a Phone Number (LC 17)

Đề bài

Cho chuỗi số 2..9. Trả về tất cả tổ hợp ký tự từ bàn phím điện thoại.

Ví dụ

Input:  digits = "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
        ('2' → "abc"; '3' → "def"; thứ tự có thể tuỳ ý)

Input:  digits = ""
Output: []

Ràng buộc

• 0 <= len(digits) <= 4
• digits chỉ chứa 2-9

Clarifying questions

• digits rỗng? → Trả [].
• Có chữ số 0/1? → Đề chỉ 2-9.

Hướng tiếp cận

Mapping {'2':'abc', ..., '9':'wxyz'}. Backtrack chọn 1 chữ cho mỗi digit.

Code Python 3

from typing import List

class Solution:
    MAP = {'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}

    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        result: list[str] = []
        path: list[str] = []

        def backtrack(i: int) -> None:
            if i == len(digits):
                result.append(''.join(path))
                return
            for ch in self.MAP[digits[i]]:
                path.append(ch)
                backtrack(i + 1)
                path.pop()

        backtrack(0)
        return result

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

• Thời gian: O(4^n · n) với n = len(digits).
• Bộ nhớ: O(n) stack.

Bình luận

• Pattern “chọn 1 từ mỗi level”: mỗi digit độc lập có lựa chọn.

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

• LC 91 - Decode Ways.

---

28.5 Combination Sum (LC 39)

Đề bài

Cho candidates (phân biệt) và target. Tìm tất cả combination tổng target. Mỗi số dùng được nhiều lần.

Ví dụ

Input:  candidates=[2,3,6,7], target=7
Output: [[2,2,3],[7]]

Ràng buộc

• 1 <= len(candidates) <= 30
• 2 <= candidates[i] <= 40
• 1 <= target <= 40

Clarifying questions

• target = 0? → Trả [[]].
• Có số = 0 trong candidates? → Vô hạn loop; theo đề ≥ 1.

Hướng tiếp cận

Backtrack với start. Cho phép dùng lại → đệ quy backtrack(i) thay vì i+1.

Code Python 3

from typing import List

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        result: list[list[int]] = []
        path: list[int] = []

        def backtrack(start: int, remain: int) -> None:
            if remain == 0:
                result.append(path.copy())
                return
            for i in range(start, len(candidates)):
                if candidates[i] > remain:
                    break               # sorted → mọi sau đều lớn
                path.append(candidates[i])
                backtrack(i, remain - candidates[i])
                path.pop()

        backtrack(0, target)
        return result

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

• Thời gian: O(N^(T/M + 1)) với N=số candidate, T=target, M=min(candidates).
• Bộ nhớ: O(T/M) stack.

Bình luận

• Bẫy: dùng backtrack(i) (không i+1) để cho phép tái sử dụng.
• Follow-up: LC 40 (Combination Sum II) cấm reuse.

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

• LC 40 - Combination Sum II (không dùng lại).
• LC 216 - Combination Sum III.

---

28.6 Palindrome Partitioning (LC 131)

Đề bài

Cho s. Trả về tất cả cách phân chia s sao cho mỗi phần là palindrome.

Ví dụ

Input:  s = "aab"
Output: [["a","a","b"], ["aa","b"]]
        (mọi cách phân chia mà mỗi phần là palindrome; thứ tự có thể tuỳ ý)

Ràng buộc

• 1 <= len(s) <= 16
• s chỉ chứa chữ thường

Clarifying questions

• s rỗng? → Trả [[]].

Hướng tiếp cận

Backtrack: tại mỗi start, thử mọi end sao cho s[start..end] palindrome, đệ quy start = end + 1.

Code Python 3

from typing import List

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        result: list[list[str]] = []
        path: list[str] = []

        def is_pal(l: int, r: int) -> bool:
            while l < r:
                if s[l] != s[r]:
                    return False
                l += 1; r -= 1
            return True

        def backtrack(start: int) -> None:
            if start == len(s):
                result.append(path.copy())
                return
            for end in range(start, len(s)):
                if is_pal(start, end):
                    path.append(s[start:end + 1])
                    backtrack(end + 1)
                    path.pop()

        backtrack(0)
        return result

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

• Thời gian: O(n · 2^n) (số partition tối đa = 2^(n-1)).
• Bộ nhớ: O(n).

Bình luận

• Tối ưu DP: precompute is_pal[i][j] O(n²), giúp tránh check lại.

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

• LC 132 - Palindrome Partitioning II (Chương 29).

---

28.7 N-Queens (LC 51)

Đề bài

Đặt n hậu trên bàn n × n sao cho không có 2 hậu nào tấn công nhau. Trả về tất cả cấu hình (mỗi cấu hình là list các string).

Ví dụ

Input:  n=4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Ràng buộc

• 1 <= n <= 9

Clarifying questions

• n = 1? → Trả 1 solution [[“Q”]].

Hướng tiếp cận

Backtrack theo hàng. Tại hàng r, thử mỗi cột c. Đảm bảo c chưa dùng, đường chéo (r - c) chưa dùng, đường chéo (r + c) chưa dùng.

Code Python 3

from typing import List

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        cols = set()
        diag1 = set()       # r - c
        diag2 = set()       # r + c
        board = [['.'] * n for _ in range(n)]
        result: List[List[str]] = []

        def backtrack(r: int) -> None:
            if r == n:
                result.append([''.join(row) for row in board])
                return
            for c in range(n):
                if c in cols or (r - c) in diag1 or (r + c) in diag2:
                    continue
                cols.add(c); diag1.add(r - c); diag2.add(r + c)
                board[r][c] = 'Q'
                backtrack(r + 1)
                board[r][c] = '.'
                cols.discard(c); diag1.discard(r - c); diag2.discard(r + c)

        backtrack(0)
        return result

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

• Thời gian: O(n!) worst.
• Bộ nhớ: O(n²) cho board + O(n) cho sets.

Bình luận

• 3 sets cho cột + 2 đường chéo - pattern kinh điển.

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

• LC 52 - N-Queens II (chỉ đếm).
• LC 37 - Sudoku Solver (bài 28.8).

---

28.8 Sudoku Solver (LC 37)

Đề bài

Giải Sudoku 9×9 in-place. Ô chưa điền là '.'.

Ví dụ

Input:  board = (ma trận 9×9, ký tự '.' cho ô trống, '1'..'9' cho số đã có)
  [['5','3','.','.','7','.','.','.','.'],
   ['6','.','.','1','9','5','.','.','.'],
   ['.','9','8','.','.','.','.','6','.'],
   ['8','.','.','.','6','.','.','.','3'],
   ['4','.','.','8','.','3','.','.','1'],
   ['7','.','.','.','2','.','.','.','6'],
   ['.','6','.','.','.','.','2','8','.'],
   ['.','.','.','4','1','9','.','.','5'],
   ['.','.','.','.','8','.','.','7','9']]

Output: board được mutate in-place thành lời giải hợp lệ
  [['5','3','4','6','7','8','9','1','2'],
   ['6','7','2','1','9','5','3','4','8'],
   ['1','9','8','3','4','2','5','6','7'],
   ['8','5','9','7','6','1','4','2','3'],
   ['4','2','6','8','5','3','7','9','1'],
   ['7','1','3','9','2','4','8','5','6'],
   ['9','6','1','5','3','7','2','8','4'],
   ['2','8','7','4','1','9','6','3','5'],
   ['3','4','5','2','8','6','1','7','9']]

(Hàm không return giá trị; chỉ mutate `board`. Mỗi hàng, mỗi cột,
 và mỗi sub-grid 3×3 đều chứa '1'..'9' đúng 1 lần.)

Ràng buộc

• board.length == 9
• Mỗi ô là ‘.’ hoặc ‘1’-‘9’

Clarifying questions

• Multiple solution? → Theo đề: chính xác 1 solution.

Hướng tiếp cận

Backtrack mỗi ô trống. Track 3 set: row, col, 3×3 box.

Code Python 3

from typing import List

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]
        empty: list[tuple[int, int]] = []
        for r in range(9):
            for c in range(9):
                if board[r][c] != '.':
                    d = board[r][c]
                    rows[r].add(d); cols[c].add(d); boxes[(r//3)*3 + c//3].add(d)
                else:
                    empty.append((r, c))

        def backtrack(i: int) -> bool:
            if i == len(empty):
                return True
            r, c = empty[i]
            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(i + 1):
                    return True
                rows[r].discard(d); cols[c].discard(d); boxes[b].discard(d)
                board[r][c] = '.'
            return False

        backtrack(0)

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

• Thời gian: O(9^(số ô trống)) worst.
• Bộ nhớ: O(81).

Bình luận

• Bài Hard nổi tiếng. Tối ưu thực sự: chọn ô có ít option nhất để đệ quy trước (MRV heuristic) - vượt khỏi phạm vi chương.

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

• LC 36 - Valid Sudoku.

---

28.9 Word Search (LC 79)

Đề bài

Cho board và word. Kiểm tra word có thể được build bằng đường đi 4 hướng không qua 1 ô 2 lần.

Ví dụ

Input:  board=[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word="ABCCED"
Output: True

Ràng buộc

• 1 <= m, n <= 6
• 1 <= len(word) <= 15

Clarifying questions

• word rỗng? → Trả True.
• board rỗng? → Trả False (nếu word khác rỗng).

Hướng tiếp cận

DFS từ mỗi ô có board[r][c] == word[0]. Backtrack: mark # rồi restore.

Code Python 3

from typing import List

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])
        DIRS = [(-1,0),(1,0),(0,-1),(0,1)]

        def dfs(r: int, c: int, i: int) -> bool:
            if i == len(word):
                return True
            if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != word[i]:
                return False
            board[r][c] = '#'
            found = any(dfs(r+dr, c+dc, i+1) for dr, dc in DIRS)
            board[r][c] = word[i]
            return found

        return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))

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

• Thời gian: O(m·n · 4^L).
• Bộ nhớ: O(L) stack.

Bình luận

• Bẫy: quên restore board sau visit → mất state.
• Tối ưu: trim sớm nếu count(ch) trong board < count(ch) trong word.

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

• LC 212 - Word Search II (Chương 23.3).

---

28.10 Word Break II (LC 140)

Đề bài

Cho s và wordDict. Trả về tất cả cách chia s thành các từ trong dict (cách nhau dấu cách).

Ví dụ

Input:  s="catsanddog", wordDict=["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]

Ràng buộc

• 1 <= len(s) <= 20
• 1 <= len(wordDict) <= 1000
• 1 <= len(wordDict[i]) <= 10

Clarifying questions

• s rỗng? → Trả [“”].
• wordDict trùng? → Dùng set tự nhiên dedupe.

Hướng tiếp cận

Backtrack với memoization (cache theo start).

Code Python 3

from functools import cache
from typing import List

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        words = set(wordDict)

        @cache
        def helper(start: int) -> List[str]:
            if start == len(s):
                return [""]
            result = []
            for end in range(start + 1, len(s) + 1):
                if s[start:end] in words:
                    for rest in helper(end):
                        result.append(s[start:end] + ("" if not rest else " " + rest))
            return result

        return helper(0)

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

• Thời gian: O(n^2 · 2^n) worst.
• Bộ nhớ: O(2^n) cache.

Bình luận

• Memo cần thiết để tránh exponential lặp lại; bài LC 139 (Word Break) chỉ check khả thi → DP O(n²).

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

• LC 139 - Word Break.

---

28.11 Restore IP Addresses (LC 93)

Đề bài

Cho chuỗi số. Liệt kê tất cả IP hợp lệ có thể tạo (4 số 0..255, mỗi số không leading zero trừ khi là “0”).

Ví dụ

Input:  s = "25525511135"   (chuỗi chỉ chứa chữ số)
Output: ["255.255.11.135", "255.255.111.35"]
        (mảng mọi IPv4 hợp lệ tạo từ s bằng cách chèn 3 dấu chấm; không leading zero)

Ràng buộc

• 1 <= len(s) <= 20
• s chỉ chứa digit

Clarifying questions

• s độ dài < 4 hoặc > 12? → Trả [].
• Có ký tự không phải số? → Theo đề: chỉ digit.

Hướng tiếp cận

Backtrack chia thành 4 phần. Mỗi phần độ dài 1, 2, hoặc 3 và thoả ràng buộc.

Code Python 3

from typing import List

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        result: list[str] = []
        path: list[str] = []

        def is_valid(p: str) -> bool:
            if len(p) > 3 or not p:
                return False
            if p[0] == '0' and len(p) > 1:
                return False
            return int(p) <= 255

        def backtrack(start: int) -> None:
            if len(path) == 4:
                if start == len(s):
                    result.append('.'.join(path))
                return
            for length in (1, 2, 3):
                if start + length > len(s):
                    break
                p = s[start:start + length]
                if is_valid(p):
                    path.append(p)
                    backtrack(start + length)
                    path.pop()

        backtrack(0)
        return result

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

• Thời gian: O(3^4) = O(81) constant.
• Bộ nhớ: O(1).

Bình luận

• Bẫy leading zero: "010" không hợp lệ; "0" hợp lệ.

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

• LC 282 - Expression Add Operators (bài 28.12).

---

28.12 Expression Add Operators (LC 282)

Đề bài

Cho chuỗi số num và target. Thêm +, -, * giữa các digit sao cho biểu thức = target. Trả về tất cả biểu thức.

Ví dụ

Input:  num="123", target=6
Output: ["1+2+3","1*2*3"]

Ràng buộc

• 1 <= len(num) <= 10
• -2^31 <= target <= 2^31-1

Clarifying questions

• target overflow? → Theo đề LC: -2^31 ≤ target ≤ 2^31-1.
• num bắt đầu bằng 0? → Có thể (như “105”); leading-zero number sẽ skip.

Hướng tiếp cận

Backtrack với 2 state phụ trợ: - cur = giá trị biểu thức cho đến giờ. - prev = giá trị của term cuối (cần để xử lý * đúng precedence).

Khi gặp +: cur += x, prev = x. Khi gặp -: cur -= x, prev = -x. Khi gặp *: cur = cur - prev + prev * x, prev = prev * x.

Code Python 3

from typing import List

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        result: list[str] = []

        def backtrack(i: int, expr: str, cur: int, prev: int) -> None:
            if i == len(num):
                if cur == target:
                    result.append(expr)
                return
            for j in range(i + 1, len(num) + 1):
                if j > i + 1 and num[i] == '0':
                    break               # leading zero
                x = int(num[i:j])
                if i == 0:
                    backtrack(j, str(x), x, x)
                else:
                    backtrack(j, expr + '+' + str(x), cur + x, x)
                    backtrack(j, expr + '-' + str(x), cur - x, -x)
                    backtrack(j, expr + '*' + str(x), cur - prev + prev * x, prev * x)

        backtrack(0, "", 0, 0)
        return result

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

• Thời gian: O(4^n) worst case (3 toán tử + bỏ qua).
• Bộ nhớ: O(n) stack.

Bình luận

• Trick cur - prev + prev * x: undo lần +/- trước (qua prev) rồi nhân.
• Bẫy leading zero: “05” không hợp lệ.

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

• LC 224 - Basic Calculator (Chương 32).

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

Backtracking schema

Thành phần	Câu hỏi cần trả lời trước khi code
Path (trạng thái hiện tại)	List / string / mask?
Choice list	Từ n phần tử, hay vị trí, hay chữ số 1..9?
Goal test	Khi nào ghi nhận / return?
Pruning / constraints	Có thể loại sớm không? Sort trước để skip dup?
Undo	Pop list, xoá set, đổi lại mask?

Decision tree (Permutations of [1,2,3])

            []
       /   |    \
      1    2     3
    / |    | \   | \
   2  3    1  3  1  2
   |  |    |  |  |  |
   3  2    3  1  2  1

Mỗi đường root→leaf = 1 permutation. Backtrack = DFS trên cây ảo này.

Duplicate handling (Subsets II / Permutations II)

Subsets II (sort + skip dup tại same level):

nums.sort()
for i in range(start, n):
    if i > start and nums[i] == nums[i-1]: continue   # cùng level, skip
    path.append(nums[i])
    dfs(i + 1)
    path.pop()

Permutations II (used array):

nums.sort()
for i in range(n):
    if used[i]: continue
    if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue  # giữ thứ tự

N-Queens / Sudoku constraint sets

• Cột: cols : set[int].
• Diag /: r + c cùng → pos_diag : set[int].
• Diag \: r - c cùng → neg_diag : set[int].
• Sudoku: thêm rows[r], cols[c], boxes[(r//3)*3 + c//3].

Expression Add Operators (LC 282) - prev_operand

Vì * ưu tiên hơn +/-, khi nhân, mình phải rút lại prev rồi nhân:

cur_total - prev_operand + prev_operand * num

---