Phỏng vấn

Mẫu quay lui (Backtracking) sinh tập con và tổ hợp trong phỏng vấn

Quay lui (Backtracking) là kỹ thuật duyệt có hệ thống qua cây quyết định bằng bộ ba thao tác: Chọn ứng viên, Đệ quy đi sâu và Hoàn tác (pop_back). Chỉ cần nắm vững cách truyền chỉ số bắt đầu start và dòng lệnh khử trùng cùng tầng i > start, bạn có thể giải trọn vẹn họ bài Subsets, Combinations và Combination Sum.

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:

  1. 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 đầu start và 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ệt i từ 0 đến n - 1 kèm mảng đánh dấu used[i].
  2. 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.
  3. 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])).
Ý chính

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ị.

Cây quyết định Backtracking: Combination Sum [2, 3, 6, 7], target = 7 path = [], rem = 7 [2]rem = 5 [3]rem = 4 [6]rem = 1: cắt [7]rem = 0 ✓ [2, 2]rem = 3 [2, 3]rem = 2: cắt [3, 3]rem = 1: cắt [2, 2, 2]rem = 1: cắt [2, 2, 3]rem = 0 ✓ Giữ i >= start để không lặp hoán vị [2, 3, 2] hay [3, 2, 2] Sắp xếp mảng tăng dần để break ngay khi a[i] > rem · Nghiệm: [2, 2, 3] và [7]
Backtracking: [2, 3, 6, 7], target = 7 Chọn (push) → Đệ quy → Hoàn tác (pop) Nhánh i = 0 (số 2): [2] → [2, 2] Chạm [2, 2, 3] (rem = 0) → Nghiệm #1 ✓ Nhánh i = 1, 2 (số 3 và 6) [3, 3] dư 1 · [6] dư 1 → Cắt tỉa a[i] > rem Nhánh i = 3 (số 7): [7] Chạm [7] (rem = 0) → Nghiệm #2 ✓ Duyệt i >= start để chống lặp hoán vị
Hình 1. Cây quyết định quay lui giải bài toán Combination Sum trên mảng đã sắp [2, 3, 6, 7] với target = 7: giữ i >= start giúp thu gọn 2 nghiệm duy nhất [2, 2, 3] và [7], đồng thời cắt tỉa sớm ngay khi a[i] > rem.

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ến start mớ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ện j > start mang giá trị false. Nhờ vậy, nút con hoàn toàn được phép chọn số 2 thứ hai để nối tiếp vào số 2 thứ 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ố 2 thứ nhất trở về vòng lặp for hiện tại, biến chạy i tăng sang vị trí của số 2 thứ hai. Lúc này i > start mang giá trị true và a[i] == a[i - 1]. Nếu ta mở tiếp nhánh này tại cùng vị trí của path, nó sẽ sinh ra tập con y hệt nhánh vừa đóng lại trước đó! Do đó lệnh continue cắ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;
}

Độ 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 n phầ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 path là O(n) (không tính bộ nhớ chứa \(2^n\) tập kết quả).
  • 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] > rem nê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

  1. Thêm trực tiếp tham chiếu path và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ủa vector<int> path.
    • Nhưng trong Python và Java, path là một tham chiếu đối tượng! Nếu bạn viết out.append(path) (Python) hoặc out.add(path) (Java), tất cả các phần tử trong out đều trỏ tới cùng một danh sách path duy nhất; và vì cuối quá trình quay lui path bị 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ết out.append(path.copy()) (hoặc list(path)), và trong Java phải viết out.add(new ArrayList<>(path)).
  2. 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.
  3. Truyền nhầm dfs(start + 1) thay vì dfs(i + 1): Trong vòng lặp for (int i = start; i < n; i++), phần tử bạn vừa chọn nằm ở vị trí i, không phải start. Nếu truyền start + 1, ở các bước lặp i > start chương trình sẽ quay lùi lại xét các phần tử trước i và 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 → 2 nghiệ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 → 3 nghiệ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 → 0 nghiệ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).

Muốn học bài bản cùng giảng viên?

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.

Xem Khóa LeetCode

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483