Nhận diện bài toán Quay lui và 3 câu hỏi phân loại cốt lõi
Khi đề bài phỏng vấn yêu cầu "liệt kê tất cả các tập con", "tìm mọi tổ hợp có tổng bằng target", "sinh mọi hoán vị" hay "tách xâu thành các đoạn đối xứng", kích thước của tập kết quả có thể tăng theo hàm mũ. Vì chương trình bắt buộc phải xây dựng và xuất ra từng cấu hình hợp lệ, không có thuật toán quy hoạch động nào thay thế được việc duyệt qua cây trạng thái bằng Quay lui (Backtracking).
Để chọn đúng khuôn code ngay trong 2 phút đầu tiên của buổi phỏng vấn, bạn hãy tự trả lời (và xác nhận với người phỏng vấn) 3 câu hỏi định hình cây đệ quy:
- Thứ tự các phần tử trong một nghiệm có quan trọng không (Tổ hợp hay Hoán vị)?
- Trong bài Tập con (Subsets) và Tổ hợp (Combinations / Combination Sum),
[2, 3]và[3, 2]được coi là cùng một tổ hợp và chỉ được in ra một lần. Để chống sinh trùng các hoán vị của cùng một tập, hàm đệ quy bắt buộc phải duy trì một chỉ số bắt đầustartvà chỉ chọn các phần tử có chỉ sối >= start. - Ngược lại, trong bài Hoán vị (Permutations),
[2, 3]và[3, 2]là hai nghiệm khác nhau, nên mỗi tầng đều duyệtitừ0đếnn - 1kèm mảng đánh dấuused[i].
- Trong bài Tập con (Subsets) và Tổ hợp (Combinations / Combination Sum),
- Mảng đầu vào có chứa các phần tử trùng nhau không?
- Trong Subsets I và Combination Sum I, đề bài đảm bảo các phần tử đầu vào đôi một phân biệt.
- Trong Subsets II và Combination Sum II, mảng đầu vào có phần tử lặp (ví dụ
[1, 2, 2]), nhưng tập kết quả lại không được chứa hai tổ hợp giống hệt nhau.
- Một phần tử được phép dùng lại nhiều lần hay chỉ tối đa 1 lần?
- Nếu được dùng vô hạn lần (như Combination Sum I), khi chọn phần tử ở vị trí
i, lời gọi đệ quy tiếp theo truyền nguyên chỉ sối(dfs(i, rem - a[i])). - Nếu mỗi phần tử trong mảng chỉ được dùng tối đa 1 lần (như Subsets, Combinations, Combination Sum II), lời gọi đệ quy tiếp theo phải tiến lên
i + 1(dfs(i + 1, rem - a[i])).
- Nếu được dùng vô hạn lần (như Combination Sum I), khi chọn phần tử ở vị trí
Khung xương của mọi bài toán tổ hợp quay lui xoay quanh hai quy tắc bất biến sau khi đã sắp xếp mảng tăng dần: (1) chỉ duyệt ứng viên từ i = start trở đi để ép các phần tử trong path luôn theo thứ tự không giảm, và (2) dùng điều kiện if (i > start && a[i] == a[i - 1]) continue; để bỏ qua các nhánh anh em cùng tầng mang cùng một giá trị.
Tại sao i > start && a[i] == a[i - 1] lại khử trùng đúng mà không làm mất nghiệm?
Khi mảng đầu vào có phần tử trùng nhau, ví dụ a = [1, 2, 2] (sau khi sắp xếp tăng dần), rất nhiều ứng viên bị rối giữa hai câu hỏi: "Tại sao tổ hợp [1, 2, 2] dùng cả hai số 2 là hợp lệ, nhưng hai tổ hợp [1, 2] (lấy số 2 thứ nhất) và [1, 2] (lấy số 2 thứ hai) lại bị tính là trùng?"
Hãy hình dung cây đệ quy theo chiều sâu (cha → con) và chiều rộng (anh → em cùng một tầng vòng lặp for):
- Khi đi xuống tầng con (gọi đệ quy
dfs(i + 1, ...)), biếnstartmới chính lài + 1. Ở đầu vòng lặp của tầng con, ứng viên đầu tiên cój == start, nên điều kiệnj > startmang giá trịfalse. Nhờ vậy, nút con hoàn toàn được phép chọn số2thứ hai để nối tiếp vào số2thứ nhất của nút cha, tạo ra nghiệm hợp lệ[1, 2, 2]. - Khi vừa quay lui (
pop_back) từ nhánh của số2thứ nhất trở về vòng lặpforhiện tại, biến chạyităng sang vị trí của số2thứ hai. Lúc nàyi > startmang giá trịtruevàa[i] == a[i - 1]. Nếu ta mở tiếp nhánh này tại cùng vị trí củapath, nó sẽ sinh ra tập con y hệt nhánh vừa đóng lại trước đó! Do đó lệnhcontinuecắt bỏ hoàn toàn nhánh anh em trùng lặp ngay từ gốc.
Đồng thời, nhờ mảng a đã được sắp xếp tăng dần (a[0] <= a[1] <= ...), trong bài Combination Sum với các số dương, hễ tại vị trí i ta gặp a[i] > rem (phần tử đang xét đã vượt quá phần tổng còn thiếu rem), thì mọi phần tử đứng sau i cũng chắc chắn lớn hơn rem. Ta có thể gọi break thoát khỏi vòng lặp for ngay lập tức (cắt tỉa nhánh — pruning) thay vì chỉ continue.
Chạy tay từng bước bài toán Combination Sum trên a = [2, 3, 6, 7], target = 7
Xét mảng a = [2, 3, 6, 7] và target = 7, mỗi số được chọn không giới hạn số lần. Ta xuất phát từ gốc với start = 0, rem = 7, path = []:
| Bước | Trạng thái (start, rem, path) |
Ứng viên i và a[i] đang thử |
Kiểm tra cắt tỉa a[i] > rem |
Hành động đệ quy / quay lui | Nghiệm thu được (out) |
|---|---|---|---|---|---|
| 1 | (0, 7, []) |
i = 0, a[0] = 2 |
2 <= 7 |
Chọn 2 → gọi dfs(0, 5, [2]) |
[] |
| 2 | (0, 5, [2]) |
i = 0, a[0] = 2 |
2 <= 5 |
Chọn 2 → gọi dfs(0, 3, [2, 2]) |
[] |
| 3 | (0, 3, [2, 2]) |
i = 0, a[0] = 2 |
2 <= 3 |
Chọn 2 → gọi dfs(0, 1, [2, 2, 2]) |
[] |
| 4 | (0, 1, [2, 2, 2]) |
i = 0, a[0] = 2 |
2 > 1 → break! |
Cắt nhánh ngay, quay lui pop() về [2, 2] |
[] |
| 5 | (0, 3, [2, 2]) |
i = 1, a[1] = 3 |
3 <= 3 |
Chọn 3 → gọi dfs(1, 0, [2, 2, 3]) → rem == 0, thu nghiệm! |
[[2, 2, 3]] |
| 6 | (0, 5, [2]) |
i = 1, a[1] = 3 |
3 <= 5 |
Chọn 3 → dfs(1, 2, [2, 3]); tại đây thử i = 1 (a[1] = 3 > 2) → break! |
[[2, 2, 3]] |
| 7 | (0, 7, []) |
i = 1, a[1] = 3 rồi i = 2, a[2] = 6 |
Các nhánh con đều chạm a[j] > rem |
Thử [3, 3] (rem = 1 < 3), [6] (rem = 1 < 6) rồi quay lui hết về [] |
[[2, 2, 3]] |
| 8 | (0, 7, []) |
i = 3, a[3] = 7 |
7 <= 7 |
Chọn 7 → gọi dfs(3, 0, [7]) → rem == 0, thu nghiệm thứ 2! |
[[2, 2, 3], [7]] |
Nhờ quy tắc chỉ thử từ start trở đi, khi ở trạng thái path = [3] (start = 1, rem = 4), vòng lặp không bao giờ quay lại xét i = 0 (a[0] = 2), nên các bộ lặp hoán vị như [3, 2, 2] hay [2, 3, 2] không bao giờ được sinh ra.
Code mẫu C++17, Python và Java 21
Chương trình dưới đây cài đặt thuật toán quay lui kết hợp sắp xếp và cắt tỉa sớm a[i] > rem cho bài toán Combination Sum trên cả 3 ngôn ngữ. Khi chạy không kèm dữ liệu đầu vào, chương trình tự kiểm tra bộ mẫu a = [2, 3, 6, 7], target = 7 và in ra 2 tổ hợp [2, 2, 3] và [7].
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
void dfs_comb(const vector<int>& a, int start, int rem,
vector<int>& path, vector<vector<int>>& out) {
if (rem == 0) {
out.push_back(path);
return;
}
for (int i = start; i < (int)a.size(); i++) {
if (i > start && a[i] == a[i - 1]) continue;
if (a[i] > rem) break;
path.push_back(a[i]);
dfs_comb(a, i, rem - a[i], path, out);
path.pop_back();
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n = 4, target = 7;
vector<int> a = {2, 3, 6, 7};
if (cin >> n >> target) {
a.resize(n);
for (auto& x : a) cin >> x;
}
sort(a.begin(), a.end());
vector<int> path;
vector<vector<int>> out;
dfs_comb(a, 0, target, path, out);
cout << out.size() << '\n';
for (const auto& comb : out) {
for (size_t i = 0; i < comb.size(); i++) {
cout << (i ? " " : "") << comb[i];
}
cout << '\n';
}
return 0;
}
import sys
def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
nums = sorted(set(candidates))
out: list[list[int]] = []
path: list[int] = []
def dfs(start: int, rem: int) -> None:
if rem == 0:
out.append(path.copy())
return
for i in range(start, len(nums)):
if nums[i] > rem:
break
path.append(nums[i])
dfs(i, rem - nums[i])
path.pop()
dfs(0, target)
return out
def main() -> None:
data = list(map(int, sys.stdin.buffer.read().split()))
if len(data) >= 2:
target = data[1]
a = data[2:]
else:
target = 7
a = [2, 3, 6, 7]
ans = combination_sum(a, target)
print(len(ans))
for comb in ans:
print(" ".join(map(str, comb)))
if __name__ == "__main__":
main()
import java.util.*;
public class Main {
static void dfsComb(int[] a, int start, int rem,
List<Integer> path, List<List<Integer>> out) {
if (rem == 0) {
out.add(new ArrayList<>(path));
return;
}
for (int i = start; i < a.length; i++) {
if (i > start && a[i] == a[i - 1]) continue;
if (a[i] > rem) break;
path.add(a[i]);
dfsComb(a, i, rem - a[i], path, out);
path.remove(path.size() - 1);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int target = 7;
int[] a = {2, 3, 6, 7};
if (sc.hasNextInt()) {
int n = sc.nextInt();
target = sc.nextInt();
a = new int[n];
for (int i = 0; i < n; i++) a[i] = sc.nextInt();
}
Arrays.sort(a);
List<List<Integer>> out = new ArrayList<>();
dfsComb(a, 0, target, new ArrayList<>(), out);
System.out.println(out.size());
for (List<Integer> comb : out) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < comb.size(); i++) {
if (i > 0) sb.append(' ');
sb.append(comb.get(i));
}
System.out.println(sb);
}
}
}
Độ phức tạp thời gian và bộ nhớ của Quay lui
Trong phỏng vấn, người phỏng vấn thường hỏi độ phức tạp của Backtracking để xem bạn có hiểu kích thước cây trạng thái hay không:
- Với bài Subsets (Sinh mọi tập con của
nphần tử):- Có tất cả \(2^n\) tập con. Để tạo bản sao mỗi tập con độ dài trung bình \(n/2\) đưa vào danh sách kết quả, thời gian tối ưu là
O(n * 2^n). - Bộ nhớ phụ cho ngăn xếp đệ quy và mảng tạm
pathlàO(n)(không tính bộ nhớ chứa \(2^n\) tập kết quả).
- Có tất cả \(2^n\) tập con. Để tạo bản sao mỗi tập con độ dài trung bình \(n/2\) đưa vào danh sách kết quả, thời gian tối ưu là
- Với bài Combination Sum (Tổng bằng
T, phần tử nhỏ nhất làM = min(a)):- Chiều cao tối đa của cây đệ quy là \(H = \lfloor T / M \rfloor\) (trường hợp xấu nhất khi cộng toàn số nhỏ nhất \(M = 1\) hoặc \(M = 2\)).
- Tại mỗi nút có tối đa \(n\) nhánh rẽ, nên số nút của cây quyết định bị chặn trên lỏng bởi \(O(n^{T/M})\), và nhờ cắt tỉa
a[i] > remnên số trạng thái thực tế được thăm nhỏ hơn rất nhiều. Bộ nhớ ngăn xếp đệ quy làO(T / M).
Bảng tổng hợp 6 biến thể Backtracking kinh điển trong phỏng vấn
Bạn có thể lưu lại bảng đối chiếu dưới đây như một tấm bản đồ tra cứu nhanh cho toàn bộ chương Quay lui trên LeetCode:
| Bài toán phỏng vấn | Sắp xếp mảng trước? | Chỉ số truyền xuống đệ quy | Điều kiện khử trùng / Đánh dấu | Khi nào ghi nhận path vào kết quả? |
|---|---|---|---|---|
| Subsets I (Không phần tử trùng) | Không bắt buộc | dfs(i + 1) |
Không cần | Ở mọi nút ngay đầu hàm dfs |
| Subsets II (Có phần tử trùng) | Bắt buộc sort |
dfs(i + 1) |
if (i > start && a[i] == a[i-1]) continue; |
Ở mọi nút ngay đầu hàm dfs |
Combinations (Chọn đúng k số từ 1..n) |
Đã tăng sẵn | dfs(i + 1) |
Cắt tỉa: i <= n - (k - path.size()) + 1 |
Khi path.size() == k |
| Combination Sum I (Dùng lại vô hạn lần) | Nên sort để cắt tỉa |
dfs(i) (giữ nguyên i) |
Cắt tỉa: if (a[i] > rem) break; |
Khi rem == 0 |
| Combination Sum II (Có trùng, dùng 1 lần) | Bắt buộc sort |
dfs(i + 1) |
i > start && a[i] == a[i-1] và a[i] > rem |
Khi rem == 0 |
| Permutations II (Hoán vị có phần tử trùng) | Bắt buộc sort |
Duyệt i từ 0..n-1 |
used[i] hoặc (i > 0 && a[i] == a[i-1] && !used[i-1]) |
Khi path.size() == n |
Những lỗi sai làm hỏng toàn bộ kết quả và cách tự kiểm tra
- Thêm trực tiếp tham chiếu
pathvào danh sách kết quả trong Python và Java (out.append(path)/out.add(path)):- Trong C++,
out.push_back(path)tự động tạo một bản sao độc lập (deep copy) củavector<int> path. - Nhưng trong Python và Java,
pathlà một tham chiếu đối tượng! Nếu bạn viếtout.append(path)(Python) hoặcout.add(path)(Java), tất cả các phần tử trongoutđều trỏ tới cùng một danh sáchpathduy nhất; và vì cuối quá trình quay luipathbịpop()về rỗng, kết quả cuối cùng của bạn sẽ là một danh sách toàn các mảng rỗng[[], [], ...]! Trong Python phải viếtout.append(path.copy())(hoặclist(path)), và trong Java phải viếtout.add(new ArrayList<>(path)).
- Trong C++,
- Quên sắp xếp mảng trước khi dùng
if (i > start && a[i] == a[i - 1]) continue;: Điều kiện so sánh phần tử liền kềa[i] == a[i - 1]chỉ gom được các số bằng nhau lại sát nhau khi mảng đã được sắp xếp tăng dần. - Truyền nhầm
dfs(start + 1)thay vìdfs(i + 1): Trong vòng lặpfor (int i = start; i < n; i++), phần tử bạn vừa chọn nằm ở vị tríi, không phảistart. Nếu truyềnstart + 1, ở các bước lặpi > startchương trình sẽ quay lùi lại xét các phần tử trướcivà sinh ra vô số tổ hợp trùng lặp.
Để tự kiểm tra code, bạn có thể đối chiếu hàm quay lui vòng lặp for với cách quay lui nhị phân 2 nhánh (tại mỗi chỉ số idx, nhánh 1 chọn nums[idx] và giữ nguyên idx, nhánh 2 bỏ qua nums[idx] và chuyển sang idx + 1) trên 3 bộ test biên:
- Bộ mẫu chuẩn
a = [2, 3, 6, 7], target = 7→2nghiệm:[2, 2, 3]và[7]. - Bộ có nhiều cách ghép từ các số nhỏ
a = [2, 3, 5], target = 8→3nghiệm:[2, 2, 2, 2],[2, 3, 3],[3, 5]. - Trường hợp không có cách ghép nào thỏa mãn
a = [2], target = 1→0nghiệm.
Thêm một bộ có phần tử trùng để chắc dòng khử trùng hoạt động: a = [2, 2, 3], target = 4 chỉ có đúng 1 nghiệm [2, 2]; nếu thiếu dòng if (i > start && a[i] == a[i - 1]) continue;, chương trình sẽ in [2, 2] ba lần.
Luyện ngay trên Big-O Coding
Hãy thực hành ngay kỹ thuật quay lui, sinh tổ hợp và tìm kiếm trên cây quyết định qua các bài tập chọn lọc trong lộ trình Coding Interview 150 dưới đây.
Câu hỏi thường gặp
Khi nào bài toán giống Combination Sum nên giải bằng Backtracking và khi nào nên giải bằng Quy hoạch động (Dynamic Programming)?
Quy tắc phân biệt rất rõ ràng: nếu đề bài yêu cầu liệt kê tất cả các tổ hợp cụ thể (như Combination Sum I, II, III), bạn bắt buộc phải dùng Backtracking để dựng từng mảng nghiệm. Ngược lại, nếu đề bài chỉ hỏi có tất cả bao nhiêu cách hoặc số lượng phần tử ít nhất để tạo ra tổng target (như Combination Sum IV hay Coin Change), việc liệt kê từng nghiệm sẽ bị quá thời gian và bạn phải chuyển sang Quy hoạch động 1 chiều (dp[rem]) trong thời gian đa thức O(n * target).
Trong bài Combinations (chọn k số từ 1..n), cắt tỉa cận trên vòng lặp i <= n - (k - path.size()) + 1 hoạt động thế nào?
Giả sử bạn cần chọn đủ k số mà hiện tại trong path đã có sz = path.size() số, nghĩa là bạn còn cần chọn thêm need = k - sz số nữa. Nếu bạn bắt đầu chọn tại giá trị i, số lượng phần tử còn lại từ i đến n là n - i + 1. Để đủ số lượng cần lấy, bắt buộc phải có n - i + 1 >= need, suy ra i <= n - need + 1. Những giá trị i lớn hơn mốc này chắc chắn không còn đủ phần tử phía sau để lấp đầy tổ hợp cỡ k, nên dừng vòng lặp sớm giúp giảm tới hơn một nửa số lời gọi đệ quy thừa.
Ngoài cách dùng đệ quy, bài Subsets có thể giải bằng thao tác bit (Bitmask) được không?
Có. Với mảng không có phần tử trùng và \(n \le 20\), mỗi tập con tương ứng 1-1 với một số nguyên mask từ 0 đến \(2^n - 1\): nếu bit thứ i của mask bật ((mask >> i) & 1), ta đưa a[i] vào tập con tương ứng. Tuy nhiên, trong phỏng vấn, cách viết Backtracking đệ quy vẫn linh hoạt hơn nhiều vì nó mở rộng trực tiếp sang bài có phần tử trùng (Subsets II) và các bài có điều kiện cắt tỉa theo tổng (Combination Sum).
Luyện LeetCode thực chiến theo pattern, giải bài trong 45 phút và mock interview cùng AI. 16 buổi online, lớp 7–12 học viên, chọn C++, Java hoặc Python.


