Subsets: ba cách xây dựng power set

Lần đầu tiên tôi giải bài này, tôi đi thẳng vào bit manipulation. Gọn, thông minh, xong trong mười phút. Rồi một người trong nhóm nhờ tôi giải thích logic, và tôi phải vẽ ba tờ nháp mới truyền đạt được ý. Cách dùng backtracking — mà lúc đầu tôi bỏ qua vì "nhiều code hơn" — lại là cách tổng quát hóa được sang tất cả các bài combination/permutation khác trong series. Bài học đó tôi vẫn giữ.

LeetCode 78 yêu cầu: cho mảng số nguyên không có phần tử trùng lặp, trả về tất cả các tập con có thể. Kết quả là power set — mọi cách chọn phần tử, bao gồm tập rỗng lẫn cả mảng.

Constraints nói gì

1 <= nums.length <= 10. Mười phần tử. Con số này có ý nghĩa thực sự.

Power set của n phần tử có 2^n tập con. Ở n=10, là 1024 tập con. Ngay cả ở O(n * 2^n) — mà cả ba cách đều đạt — bạn tốn nhiều nhất 10.240 phép toán. Không cần tối ưu gì thêm để đảm bảo thời gian. Constraint này không thắt chặt yêu cầu; nó đang cho phép bạn làm gì cũng được. Mọi thuật toán sinh đúng tất cả các tập con đều đủ nhanh, nên lựa chọn giữa các cách phụ thuộc vào tính rõ ràng và khả năng tổng quát hóa, không phải hiệu năng thô.

Tất cả phần tử đều unique. Không cần xử lý dedup. Nếu có duplicates, bạn sẽ cần thêm logic (đó là LeetCode 90, Subsets II). Ở đây, mỗi cách chọn index khác nhau cho một tập con khác nhau.

Giá trị từ -10 đến 10. Không ảnh hưởng đến thuật toán — số âm hoạt động tốt trong cả ba cách.

Bit manipulation: mỗi số nguyên là một mask

Mỗi tập con của n phần tử có thể biểu diễn bằng một số n-bit. Bit j được set nghĩa là nums[j] được chọn. Số nguyên 0 (tất cả bit bằng 0) là tập rỗng. Số nguyên 2^n - 1 (tất cả bit bằng 1) là cả mảng. Duyệt từ 0 đến 2^n - 1 và trích xuất phần tử tương ứng sẽ cho mọi tập con đúng một lần.

class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        n = len(nums)
        result = []
        for mask in range(1 << n):  # 0 đến 2^n - 1
            subset = []
            for j in range(n):
                if mask & (1 << j):
                    subset.append(nums[j])
            result.append(subset)
        return result

public class Solution {
    public IList<IList<int>> Subsets(int[] nums) {
        int n = nums.Length;
        var result = new List<IList<int>>();
        int total = 1 << n;
        for (int mask = 0; mask < total; mask++) {
            var subset = new List<int>();
            for (int j = 0; j < n; j++) {
                if ((mask & (1 << j)) != 0)
                    subset.Add(nums[j]);
            }
            result.Add(subset);
        }
        return result;
    }
}

Với nums = [1, 2, 3]:

• mask = 0 (000) -> []
• mask = 1 (001) -> [1]
• mask = 2 (010) -> [2]
• mask = 3 (011) -> [1, 2]
• mask = 4 (100) -> [3]
• mask = 5 (101) -> [1, 3]
• mask = 6 (110) -> [2, 3]
• mask = 7 (111) -> [1, 2, 3]

Đúng tám tập con như kỳ vọng.

Time: O(n _ 2^n) — 2^n mask, mỗi cái cần quét n bit. Space: O(n _ 2^n) cho output. Stack không đáng kể; allocation duy nhất đáng kể là kết quả.

Tôi dùng cách này khi cần viết nhanh trong môi trường scripting và người đọc quen với bitwise ops. Trong code production hoặc phỏng vấn mà cần mở rộng thêm điều kiện, tôi sẽ không chọn nó — logic "chọn/bỏ" không hiển thị rõ ràng và không tổng quát hóa sạch khi cần thêm constraint như "tập con có tổng bằng k."

Backtracking: cây quyết định include/exclude

Tại mỗi phần tử, bạn đưa ra một quyết định nhị phân: đưa nó vào tập con hiện tại, hoặc bỏ qua. Đệ quy cả hai nhánh. Khi bạn đã quyết định xong cho mọi phần tử, tập con hiện tại đã hoàn chỉnh — ghi lại một bản copy.

Cây đệ quy cho [1, 2, 3]:

Tám lá, tám tập con. Mỗi lá đạt được sau đúng n quyết định.

class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        result = []
        current = []
 
        def backtrack(index: int) -> None:
            if index == len(nums):
                result.append(current[:])  # copy — không phải reference
                return
            # bỏ qua nums[index]
            backtrack(index + 1)
            # lấy nums[index]
            current.append(nums[index])
            backtrack(index + 1)
            current.pop()  # undo — backtrack
 
        backtrack(0)
        return result

public class Solution {
    public IList<IList<int>> Subsets(int[] nums) {
        var result = new List<IList<int>>();
        var current = new List<int>();
 
        void Backtrack(int index) {
            if (index == nums.Length) {
                result.Add(new List<int>(current));  // copy
                return;
            }
            // bỏ qua nums[index]
            Backtrack(index + 1);
            // lấy nums[index]
            current.Add(nums[index]);
            Backtrack(index + 1);
            current.RemoveAt(current.Count - 1);  // undo
        }
 
        Backtrack(0);
        return result;
    }
}

Trace từng bước với [1, 2, 3]:

backtrack(0)
  bỏ 1 → backtrack(1)
    bỏ 2 → backtrack(2)
      bỏ 3 → backtrack(3)  →  ghi []
      lấy 3 → backtrack(3)  →  ghi [3],  pop 3
    lấy 2 → backtrack(2)
      bỏ 3 → backtrack(3)  →  ghi [2]
      lấy 3 → backtrack(3)  →  ghi [2,3],  pop 3
      pop 2
  lấy 1 → backtrack(1)
    bỏ 2 → backtrack(2)
      bỏ 3 → backtrack(3)  →  ghi [1]
      lấy 3 → backtrack(3)  →  ghi [1,3],  pop 3
    lấy 2 → backtrack(2)
      bỏ 3 → backtrack(3)  →  ghi [1,2]
      lấy 3 → backtrack(3)  →  ghi [1,2,3],  pop 3
      pop 2
    pop 1

Mỗi pop() trong trace là bước backtrack — nó hoàn tác append từ nhánh lấy để lần gọi tiếp theo bắt đầu với current sạch. current[:] copy tại lá là bắt buộc: nếu không, bạn đang thêm cùng một object list tám lần, và tất cả tám entry trong result đều trỏ vào current sau lần backtrack cuối cùng.

Time: O(n _ 2^n). Space: O(n _ 2^n) cho output cộng O(n) độ sâu recursion stack — tổng bị chi phối bởi output.

Đây là cách tôi sẽ dùng và là cái đáng thuộc lòng. Pattern include/exclude ánh xạ trực tiếp sang Subsets II (thêm sort + bỏ qua phần tử trùng cùng depth), Combination Sum (thêm tham số tổng còn lại), và Permutations (thay include/exclude bằng gán vị trí). Khi bạn đã nắm vững skeleton backtracking, các bài biến thể chỉ khác một hoặc hai dòng.

Iterative expansion

Bắt đầu với tập rỗng. Xử lý từng phần tử một: với mỗi tập con hiện có trong result, tạo một tập con mới là tập con đó cộng phần tử hiện tại. Thêm các tập con mới vào result. Lặp lại.

Sau xử lý 1: [[], [1]]
Sau xử lý 2: [[], [1], [2], [1,2]]
Sau xử lý 3: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        result: list[list[int]] = [[]]
        for num in nums:
            new_subsets = [subset + [num] for subset in result]
            result.extend(new_subsets)
        return result

public class Solution {
    public IList<IList<int>> Subsets(int[] nums) {
        var result = new List<IList<int>> { new List<int>() };
        foreach (int num in nums) {
            int count = result.Count;
            for (int i = 0; i < count; i++) {
                var newSubset = new List<int>(result[i]) { num };
                result.Add(newSubset);
            }
        }
        return result;
    }
}

Time: O(n _ 2^n). Space: O(n _ 2^n). Không có recursion nên không cần lo stack — dù ở n=10 stack của backtracking chỉ sâu 10 frame, hoàn toàn không đáng kể.

Cách iterative dễ tự thuyết phục nhất về tính đúng đắn: bạn có thể thấy result lớn dần từng bước. Nhưng nó không tổng quát hóa tốt như backtracking. Thêm constraint "chỉ tập con có kích thước k" đòi phải lọc sau, thay vì prune sớm trong quá trình tìm kiếm. Với bài này thì ổn — n=10, bạn có thể chịu phần dư đó. Với các biến thể lớn hơn hoặc có nhiều điều kiện, iterative expansion trở nên cồng kềnh.

Edge cases

Một phần tử (nums = [0]): cả ba cách đều sinh [[], [0]] đúng. Bit mask chạy mask=0 (rỗng) và mask=1 (lấy index 0). Backtracking tạo hai lần gọi ở depth 0: bỏ sinh [], lấy sinh [0]. Iterative bắt đầu với [[]] rồi thêm [[0]].

n tối đa = 10: 1024 tập con, mỗi cái dài tối đa 10 phần tử. Python và C# xử lý không vấn đề gì. List kết quả là allocation duy nhất đáng kể — khoảng 10KB list trong trường hợp tệ nhất.

Giá trị âm (nums = [-1, 0, 1]): không có gì trong cả ba cách giả định giá trị không âm. Bit mask index theo vị trí, không theo giá trị. Backtracking append bất kỳ nums[index] nào. Iterative nối bất kỳ num nào. Tất cả ba cách đều hoạt động không thay đổi.

Phần tử ở giá trị cực đoan: nums có thể chứa bất kỳ số nguyên nào từ -10 đến 10. Constraint đảm bảo tất cả phần tử là distinct, nên không có vấn đề dedup ngay cả ở biên.

So sánh

Cả ba có độ phức tạp asymptotic giống nhau vì output bản thân đã là O(n * 2^n) — không thể tốt hơn khi phải sinh mọi tập con. Constant factor khác nhau đôi chút: iterative expansion cấp phát list trung gian trong bước extend, trong khi backtracking tái sử dụng một list current duy nhất. Trong thực tế ở n=10, điều này hoàn toàn không quan trọng.

Điểm phân biệt thực sự là khả năng mang pattern đi xa được bao nhiêu. Backtracking là cái cần nắm.

Vị trí trong series backtracking

Subsets là điểm vào sạch nhất cho backtracking vì cấu trúc include/exclude là nhị phân và không có điều kiện — không có pruning, không có constraint, chỉ là hai lựa chọn mỗi phần tử. Đó là lý do bài này là bài đầu tiên trong series.

Từ đây tiến trình tự nhiên là:

• Subsets II (LeetCode 90): cấu trúc tương tự nhưng mảng có thể có duplicates. Thêm sort, rồi bỏ qua các phần tử bằng nhau liên tiếp ở cùng depth recursion để tránh tập con trùng. Chỉ thêm một guard trong hàm backtrack.
• Combinations (LeetCode 77): sinh tất cả tập con có đúng kích thước k. Thêm kiểm tra kích thước vào base case; prune nhánh sớm khi len(current) + phần_tử_còn_lại < k.
• Combination Sum (LeetCode 39): tìm tất cả tập con có tổng bằng target. Thêm tham số tổng đang chạy; prune khi tổng vượt target. Phần tử có thể dùng lại, nên lần gọi đệ quy không tăng index.
• Permutations (LeetCode 46): thay vì include/exclude theo index, gán vị trí. Mỗi lần gọi đệ quy chọn một phần tử chưa dùng cho vị trí hiện tại. Model tư duy include/exclude chuyển thành mảng boolean "used" hoặc swap in-place.

Skeleton giữ nguyên qua tất cả: một current state, một lần gọi đệ quy mở rộng nó, và một bước undo/backtrack. Subsets là nơi bạn nội hóa skeleton đó trước khi các constraint làm mọi thứ phức tạp hơn.