Cho một tập hợp các số nguyên candidates và một số nguyên target. Tìm tất cả các tổ hợp từ candidates sao cho tổng các phần tử trong tổ hợp bằng target. Mỗi số trong candidates chỉ có thể được sử dụng một lần trong mỗi tổ hợp. Lưu ý: Kết quả không được chứa các tổ hợp trùng lặp.

Để giải quyết bài toán này, chúng ta sẽ sử dụng phương pháp quay lui (backtracking). Phương pháp này giúp chúng ta khám phá tất cả các khả năng một cách hệ thống, đồng thời loại bỏ các nhánh không dẫn đến kết quả (cắt tỉa - pruning) để tối ưu hóa.

Đệ quy ba giai đoạn

Hàm đệ quy: timCacTongHop(int[] mangSo, int mucTieu, int chiSoBatDau, int tongHienTai, int[] daSuDung)

• Xác định tham số và giá trị trả về:
• Tham số:
• mangSo: Mảng chứa các số ứng cử viên.
• mucTieu: Mục tiêu tổng cần đạt.
• chiSoBatDau: Chỉ số bắt đầu trong mảng mangSo để chọn phần tử trong lần đệ quy hiện tại.
• tongHienTai: Tổng của các phần tử đã được thêm vào tổ hợp tạm thời.
• daSuDung: Mảng đánh dấu, chỉ ra xem một phần tử đã được sử dụng trong tổ hợp hiện tại hay chưa.
• Giá trị trả về: Hàm này không cần giá trị trả về. Chúng ta sẽ sử dụng một danh sách toàn cục ketQua để lưu trữ các tổ hợp hợp lệ và một danh sách tongHopHienTai để lưu trữ tổ hợp đang được xây dựng.
• Xác định điểm dừng đệ quy:
• Khi chiSoBatDau bằng độ dài của mảng mangSo, nghĩa là không còn phần tử nào để xem xét, chúng ta dừng quá trình đệ quy.
• Logic đệ quy trong một lớp:
• Cách 1: Sử dụng mảng daSuDung để loại bỏ trùng lặp ở cấp độ cây: Mảng mangSo cần được sắp xếp trước khi thực hiện quay lui. Do việc cắt tỉa đã yêu cầu sắp xếp, nên mảng đã ở trạng thái sắp xếp.

// Vòng lặp để duyệt qua các phần tử
for (int i = chiSoBatDau; i < mangSo.length; i++) {
    // Cắt tỉa: Nếu tổng hiện tại cộng với phần tử hiện tại vượt quá mục tiêu, dừng vòng lặp.
    // Vì mảng đã được sắp xếp, các phần tử sau sẽ lớn hơn, không thể tạo ra tổng hợp hợp lệ.
    if (tongHienTai + mangSo[i] > mucTieu) {
        break;
    }
    // Loại bỏ trùng lặp ở cấp độ cây: Nếu phần tử hiện tại trùng với phần tử trước đó
    // và phần tử trước đó chưa được sử dụng trong tổ hợp hiện tại, bỏ qua.
    if (i > 0 && mangSo[i - 1] == mangSo[i] && daSuDung[i - 1] == 0) {
        continue;
    }
    // Đánh dấu phần tử hiện tại là đã sử dụng
    daSuDung[i] = 1;
    tongHopHienTai.add(mangSo[i]);
    // Gọi đệ quy để tiếp tục xây dựng tổ hợp
    timCacTongHop(mangSo, mucTieu, i + 1, tongHienTai + mangSo[i], daSuDung);
    // Quay lui: Bỏ đánh dấu và loại bỏ phần tử khỏi tổ hợp tạm thời
    daSuDung[i] = 0;
    tongHopHienTai.remove(tongHopHienTai.size() - 1);
}

• Cách 2: Sử dụng mảng daSuDung được định nghĩa trong mỗi lần đệ quy:

// Khởi tạo mảng `daSuDung` trong mỗi lần gọi hàm
int[] daSuDung = new int[60]; // Kích thước mảng phụ thuộc vào phạm vi giá trị của phần tử.
// Vòng lặp để duyệt qua các phần tử
for (int i = chiSoBatDau; i < mangSo.length; i++) {
    // Cắt tỉa:
    if (tongHienTai + mangSo[i] > mucTieu) {
        break; // Tương tự như trên, dừng vòng lặp nếu tổng vượt quá mục tiêu.
    }
    // Loại bỏ trùng lặp ở cấp độ cây: Nếu phần tử này đã được sử dụng trong lần duyệt hiện tại, bỏ qua.
    if (daSuDung[mangSo[i]] == 1) {
        continue;
    }
    // Đánh dấu phần tử hiện tại là đã sử dụng
    daSuDung[mangSo[i]] = 1;
    tongHopHienTai.add(mangSo[i]);
    // Gọi đệ quy để tiếp tục xây dựng tổ hợp
    timCacTongHop(mangSo, mucTieu, i + 1, tongHienTai + mangSo[i], daSuDung);
    // Quay lui: Loại bỏ phần tử khỏi tổ hợp tạm thời.
    // Lưu ý: Chúng ta không cần đặt lại `daSuDung[mangSo[i]] = 0` ở đây.
    // Vì `daSuDung` phục vụ cho lần đệ quy hiện tại, nó chỉ đánh dấu xem một giá trị cụ thể đã được sử dụng trong lớp này hay chưa.
    // Ví dụ: `mangSo`:[1,1,2,3,4]; `daSuDung[1]=1` có nghĩa là giá trị 1 đã được thêm vào `tongHopHienTai`.
    // Chúng ta không thể đặt lại nó thành 0, nếu không vòng lặp tiếp theo sẽ chọn phần tử 1 thứ hai, gây ra trùng lặp.
    tongHopHienTai.remove(tongHopHienTai.size() - 1);
}