Quay lui tìm tổ hợp có tổng bằng Target (Combination Sum)

Mục tiêu kiến thức

• Triển khai thuật toán quay lui (Backtracking) có tỉa nhánh (Pruning) hiệu quả.
• Phân biệt hai chiến lược: tái sử dụng phần tử không giới hạn (allow_reuse=True) và mỗi phần tử dùng tối đa 1 lần (allow_reuse=False).
• Khử trùng lặp tổ hợp khi mảng đầu vào chứa các số trùng nhau.

Mô tả bài toán

Viết hàm combination_sum(candidates: list[int], target: int, allow_reuse: bool = True) -> list[list[int]]:

• Tìm tất cả các tổ hợp duy nhất các số trong candidates sao cho tổng bằng target.
• Chế độ allow_reuse:
• allow_reuse=True: Mỗi số trong candidates có thể được dùng không giới hạn số lần.
• allow_reuse=False: Mỗi số tại một vị trí chỉ được dùng tối đa 1 lần. Mảng candidates có thể chứa các số trùng nhau, nhưng danh sách tổ hợp trả về không được chứa các tổ hợp trùng lặp.
• Chuẩn hóa đầu ra:
• Các số trong mỗi tổ hợp được sắp xếp tăng dần.
• Danh sách các tổ hợp được sắp xếp theo thứ tự từ điển (lexicographical).
• Nếu target <= 0 hoặc không có tổ hợp nào thỏa mãn, trả về [].

Ràng buộc

• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào tuân thủ đúng kiểu dữ liệu và miền giá trị được mô tả.