Sinh tất cả các tập con bằng thuật toán Quay lui

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

• Hiểu mô hình Cây không gian trạng thái (State-space Tree) trong thuật toán Đệ quy Quay lui (Backtracking).
• Nắm vững chu trình 3 bước kinh điển: Chọn (Choose) → Đệ quy (Explore) → Bỏ chọn (Unchoose/Backtrack).
• Khắc phục bẫy lưu tham chiếu đối tượng khả biến trong Python: luôn lưu bản sao current.copy() hoặc list(current).

Mô tả bài toán

Trong bài toán tinh chỉnh siêu tham số (Hyperparameter Grid Search) tại AI Empire Academy, cần sinh toàn bộ các tổ hợp tập con (Power Set) của một tập các tham số đầu vào.

Cho danh sách các số nguyên phân biệt nums. Hãy viết hàm generate_subsets(nums: list[int]) -> list[list[int]] sinh tất cả các tập hợp con khả dĩ của nums bằng thuật toán Quay lui.

Quy tắc:

• Tập con rỗng [] và tập con đầy đủ chính là hai tập con hợp lệ.
• Với mảng có N phần tử, kết quả phải có đúng 2^N tập con.
• Để đảm bảo tính nhất quán khi chấm bài:
• Sắp xếp mảng nums ban đầu theo thứ tự tăng dần trước khi quay lui.
• Các tập con trong kết quả trả về được sắp xếp theo thứ tự từ điển (Lexicographical order).

Ràng buộc

• 0 ≤ len(nums) ≤ 12.
• Các phần tử trong nums là duy nhất.
• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.