Giới thiệu

Cho một mảng số nguyên nums với các phần tử khác nhau. Hãy trả về tất cả tập con có thể có (power set) của mảng đó.

Yêu cầu: Kết quả không chứa tập con trùng lặp. Bạn có thể trả về kết quả theo bất kỳ thứ tự nào.

Ví dụ 1:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Ví dụ 2:

Input: nums = [0]
Output: [[],[0]]

Ràng buộc:

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• Các phần tử trong nums khác nhau

Giải thuật: Backtracking with "Pick or Skip"

Ý tưởng chính

Với mỗi phần tử trong mảng, chúng ta chỉ có hai lựa chọn duy nhất:

• Bỏ qua phần tử đó, không thêm vào tập con hiện tại.
• Chọn phần tử đó, thêm nó vào tập con hiện tại, sau đó xóa nó khỏi tập con khi quay lui (backtrack).

Cây quyết định nhị phân đại diện cho quá trình này:

• Nhánh trái: Bỏ qua phần tử.
• Nhánh phải: Chọn phần tử.
• Chúng ta đi đến lá khi duyệt hết tất cả các phần tử, tức là quyết định đã được đưa ra cho tất cả.

Các bước thực hiện

1. Base Case: Khi chỉ số i bằng độ dài của mảng, tức là chúng ta đã quyết định xong cho mọi phần tử. Lúc này, tập con hiện tại (lưu trong path) là một phương án hoàn chỉnh, cần được sao chép sâu (deep copy) và thêm vào danh sách kết quả ans.
2. Nhánh 1 - Bỏ qua phần tử hiện tại: Gọi đệ quy backtrack(i + 1) mà không thay đổi path.
3. Nhánh 2 - Chọn phần tử hiện tại:
   • Thêm nums[i] vào cuối path.
   • Gọi đệ quy backtrack(i + 1).
   • Xóa phần tử vừa thêm khỏi path (quay lui) để khôi phục trạng thái trước đó cho các nhánh khác.

Mã nguồn minh họa (Java)

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> currentSubset = new ArrayList<>();
        backtrack(0, nums, currentSubset, ans);
        return ans;
    }

    // i: chỉ số phần tử đang xem xét
    private void backtrack(int i, int[] nums, List<Integer> current, List<List<Integer>> answer) {
        // Base case: đã quyết định xong cho tất cả phần tử
        if (i == nums.length) {
            // Tạo bản sao (deep copy) của tập con hiện tại và thêm vào kết quả
            answer.add(new ArrayList<>(current));
            return;
        }

        // Nhánh 1: Không chọn phần tử hiện tại
        backtrack(i + 1, nums, current, answer);

        // Nhánh 2: Chọn phần tử hiện tại
        current.add(nums[i]);               // Đưa ra quyết định "chọn"
        backtrack(i + 1, nums, current, answer); // Gọi đệ quy
        current.remove(current.size() - 1); // Quay lui: thu hồi quyết định
    }
}

Phân tích độ phức tạp

• Thời gian: O(n * 2^n). Mỗi phần tử có 2 lựa chọn, tổng số tập con là 2^n. Việc sao chép mỗi tập con tốn O(n).
• Không gian: O(n). Độ sâu tối đa của stack đệ quy là n, ngoài ra còn có mảng current để lưu tập con tạm thời.

Ví dụ mô phỏng với nums = [1, 2]

1. backtrack(0): Xem xét phần tử 1.
   • Nhánh "Không chọn 1": Gọi backtrack(1).
     • backtrack(1): Xem xét phần tử 2.
       • Nhánh "Không chọn 2": Gọi backtrack(2) -> Base case: thêm [].
       • Nhánh "Chọn 2": current = [2], gọi backtrack(2) -> Base case: thêm [2] -> quay lui (pop 2).
   • Nhánh "Chọn 1": current = [1], gọi backtrack(1).
     • backtrack(1): Xem xét phần tử 2.
       • Nhánh "Không chọn 2": Gọi backtrack(2) -> Base case: thêm [1].
       • Nhánh "Chọn 2": current = [1,2], gọi backtrack(2) -> Base case: thêm [1,2] -> quay lui (pop 2).

Kết quả cuối cùng: [[], [2], [1], [1,2]]

Những điểm cần lưu ý

• Thời điểm thêm vào kết quả: Trong giải pháp "Chọn / Bỏ qua" này, chỉ thêm khi đến base case (lá của cây). Các tập con trung gian không được thêm vào.
• Thứ tự nhánh: Có thể xử lý nhánh "Chọn" trước hoặc "Bỏ qua" trước; kết quả vẫn như nhau. Thường viết "Bỏ qua" trước để code gọn hơn (không cần thao tác add/remove).
• So sánh với vòng lặp for: Cách tiếp cận này dùng cây nhị phân, khác với phương pháp dùng vòng lặp for ở mỗi bước.