Giới thiệu về giải thuật quay lui

Giải thuật quay lui (backtracking) và đệ quy có mối quan hệ mật thiết với nhau. Bất cứ nơi nào có đệ quy, thường sẽ có sự quay lui, và nó thường xuất hiện ngay sau lời gọi đệ quy.

Giải thuật này thường được áp dụng để giải quyết các loại bài toán như:

• Bài toán kết hợp
• Bài toán chia cắt (partitioning)
• Bài toán tập con
• Bài toán hoán vị
• Bài toán bàn cờ (như N-queens)

Kết hợp: [1, 2] và [2, 1] được coi là cùng một kết hợp.

Hoán vị: [1, 2] và [2, 1] được coi là hai hoán vị khác nhau.

Về bản chất, giải thuật quay lui là một phương pháp tìm kiếm vét cạn.

Ví dụ, với các số 1, 2, 3, 4, hãy tìm tất cả các kết hợp có kích thước 2.

Bài toán chia cắt: Cho một chuỗi, hỏi có bao nhiêu cách chia cắt hoặc làm thế nào để đảm bảo các chuỗi con đều là palindrome.

Cấu trúc cây của giải thuật quay lui

Giải thuật quay lui có thể được trừu tượng hóa thành cấu trúc cây N-phân.

• Chiều rộng của cây tương ứng với kích thước của tập hợp đang được xử lý, sử dụng vòng lặp for.
• Chiều sâu của cây tương ứng với độ sâu của đệ quy, vì đệ quy luôn có điểm dừng và trả về kết quả từng tầng một.

Mẫu giải thuật quay lui

Hàm quay lui thường không có giá trị trả về và thường được đặt tên là backtrack. Tham số thường rất nhiều và khó xác định ngay lập tức.

void backtrack(Tham số) {
    if (Điều kiện dừng) {
        Thu thập kết quả;
        return;
    }
    
    for (Lựa chọn : các phần tử trong tập hợp hiện tại) {
        Xử lý nút;
        backtrack(Đường đi, Danh sách lựa chọn);
        Quay lui, hoàn tác xử lý;
    }
}

Vòng lặp for duyệt qua các phần tử trong tập hợp, số lần lặp tương ứng với số nút con của một nút.

LC 77 - Kết hợp

Đề bài: Cho hai số nguyên n và k, trả về tất cả các kết hợp có k phần tử từ các số từ 1 đến n.

Ví dụ: Đầu vào: n = 4, k = 2
Đầu ra: [[2,4], [3,4], [2,3], [1,2], [1,3], [1,4]]

Một giải pháp đơn giản nhưng không hiệu quả là sử dụng nhiều vòng lặp for. Ví dụ với k=2, ta dùng 2 vòng lặp. Nhưng nếu k=50, liệu có thể viết 50 vòng lặp?

Áp dụng giải thuật quay lui

Giải thuật quay lui sử dụng đệ quy để kiểm soát số lượng vòng lặp. Mỗi lần đệ quy tương ứng với một vòng lặp ở tầng tiếp theo.

Các bước triển khai giải thuật quay lui

1. Xác định tham số và giá trị trả lời của hàm đệ quy
   • Thông thường, hàm không trả về giá trị (void), tên hàm thường là backtrack
2. Xác định điều kiện dừng
   • Khi đạt đến nút lá, tức là khi đường dẫn có kích thước bằng k
3. Xác định logic tìm kiếm ở mỗi tầng
   • Sử dụng startIndex để kiểm soát điểm bắt đầu của mỗi vòng lặp
   • Tầng tiếp theo sẽ truyền vào startIndex = i + 1

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> current = new ArrayList<>();
        backtrack(n, k, 1, result, current);
        return result;        
    }
    
    private void backtrack(int n, int k, int startIndex, List<List<Integer>> result, List<Integer> current) {
        if (current.size() == k) {
            result.add(new ArrayList<>(current));
            return;
        }
        
        for (int i = startIndex; i <= n; i++) {
            current.add(i);
            backtrack(n, k, i + 1, result, current);
            current.remove(current.size() - 1); // Xóa phần tử cuối
        }
    }
}

Tối ưu hóa (Cắt tỉa)

Với n = 4, k = 4, ở tầng đầu tiên của vòng lặp, việc duyệt từ phần tử 2 trở đi là không cần thiết. Ở tầng thứ hai, việc duyệt từ phần tử 3 trở đi cũng không cần thiết.

Quy trình tối ưu:

1. Số phần tử đã chọn: current.size()
2. Số phần tử còn cần: k - current.size()
3. Vị trí bắt đầu tối đa trong tập hợp n: n - (k - current.size()) + 1

Tại sao có +1? Vì vị trí bắt đầu được tính vào, chúng ta sử dụng tập hợp đóng bên trái.

Ví dụ, n = 4, k = 3, đã chọn 0 phần tử, n - (k - 0) + 1 = 4 - 3 + 1 = 2. Việc bắt đầu từ vị trí 2 là hợp lý, có thể tạo thành kết hợp [2, 3, 4].

Để cắt tỉa, chỉ cần điều chỉnh phạm vi của vòng lặp:

for (int i = startIndex; i <= n - (k - current.size()) + 1; i++)

LC 216 - Tổng kết hợp III

Đề bài: Tìm tất cả các kết hợp gồm k số có tổng bằng n. Kết hợp chỉ chứa các số nguyên dương từ 1-9 và không có số nào lặp lại.

Điều kiện:

• Tất cả các số đều là số nguyên dương
• Bộ giải không chứa các kết hợp trùng lặp

Ví dụ 1: Đầu vào: k = 3, n = 7
Đầu ra: [[1,2,4]]

Ví dụ 2: Đầu vào: k = 3, n = 9
Đầu ra: [[1,2,6], [1,3,5], [2,3,4]]

Khác biệt so với bài LC77 là bài toán này có ràng buộc về tổng, yêu cầu tìm các kết hợp có tổng bằng n.

public List<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> current = new ArrayList<>();
    backtrack(k, n, 1, 0, result, current);
    return result;
}

private void backtrack(int k, int n, int startIndex, int currentSum, List<List<Integer>> result, List<Integer> current) {
    if (currentSum > n) return;
    
    if (current.size() == k) {
        if (currentSum == n) {
            result.add(new ArrayList<>(current));
        }
        return;
    }
    
    for (int i = startIndex; i <= 9; i++) {
        current.add(i);
        currentSum += i;
        backtrack(k, n, i + 1, currentSum, result, current);
        current.remove(current.size() - 1);
        currentSum -= i;
    }
}

Tối ưu hóa (Cắt tỉa)

1. if (currentSum > n) return;
2. i <= 9 - (k - current.size()) + 1;

LC 17 - Kết hợp chữ số điện thoại

Đề bài: Cho một chuỗi chỉ chứa các số từ 2-9, trả về tất cả các kết hợp chữ cái mà nó có thể biểu diễn.

Ánh xạ số sang chữ cái như sau (tương tự bàn phím điện thoại):

Ví dụ:

• Đầu vào: "23"
• Đầu ra: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

Đầu tiên, cần giải quyết vấn đề ánh xạ: số 2 tương ứng với abc, số 3 tương ứng với def, v.v.

String[] digitToLetters = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

Tại sao cần cả vị trí 0 và 1? Vì chúng ta sử dụng chỉ số mảng, số 2 sẽ tương ứng với "abc".

Biến index dùng để theo dõi đang xử lý chữ số thứ mấy trong chuỗi đầu vào, đồng thời也表示 chiều sâu của cây.

Điều kiện dừng là khi index bằng độ dài chuỗi đầu vào (digits.length()). Khi đó, ta thu thập kết quả và kết thúc đệ quy tại tầng đó.

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        StringBuilder combination = new StringBuilder();
        
        if (digits == null || digits.length() == 0) return result;
        
        String[] digitToLetters = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        backtrack(digits, digitToLetters, 0, result, combination);
        return result;
    }
    
    private void backtrack(String digits, String[] digitToLetters, int index, List<String> result, StringBuilder combination) {
        if (index == digits.length()) {
            result.add(combination.toString());
            return;
        }
        
        String letters = digitToLetters[digits.charAt(index) - '0'];
        for (int i = 0; i < letters.length(); i++) {
            combination.append(letters.charAt(i));
            backtrack(digits, digitToLetters, index + 1, result, combination);
            combination.deleteCharAt(combination.length() - 1);
        }
    }
}