Subsets II: một điều kiện skip làm thay đổi tất cả

LeetCode 78 (Subsets) khá gọn gàng — mọi phần tử đều unique, nên mỗi lựa chọn chỉ số phân biệt sẽ tạo ra một tập con phân biệt. LeetCode 90 phá vỡ giả định đó. Input có thể có phần tử trùng nhau, nhưng output thì không được. Một thay đổi nhỏ trong đề bài — "có thể chứa duplicate" — nhưng lại đặt ra vấn đề khá tinh tế trong implementation.

Con đường dễ thấy nhất là: sinh tất cả, rồi loại trùng. Nó hoạt động, đơn giản, nhưng lại tạo thói quen sai cho phần còn lại của backtracking series. Giải pháp tốt hơn là không bao giờ sinh ra các tập con trùng ngay từ đầu. Một điều kiện skip duy nhất — i > start and nums[i] == nums[i-1] — làm toàn bộ công việc. Hãy cùng xem tại sao nó đúng, tại sao i > 0 lại sai, và khi nào thì dùng cái nào.

Đề bài

Cho một mảng số nguyên nums có thể chứa phần tử trùng lặp, trả về tất cả các tập con (power set) sao cho kết quả không chứa tập con trùng nhau. Full statement: LeetCode 90.

Ràng buộc:
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10

Constraints nói gì về bài này

1 <= nums.length <= 10 và -10 <= nums[i] <= 10. Cùng kích thước với Subsets (78), cùng dải giá trị.

n = 10 nghĩa là 2^10 = 1024 tập con có thể có trong trường hợp không có duplicate. Thêm duplicate thì số tập con phân biệt giảm xuống, nhưng không gian tìm kiếm vẫn là 2^n. Ở O(n * 2^n) bạn chỉ làm tối đa 10 * 1024 = 10,240 phép toán — không cần tối ưu về hiệu suất. Constraint đang cho bạn phép dùng bất kỳ thuật toán nào miễn là đúng.

Constraint quan trọng nhất ở đây là sự kết hợp giữa "input có thể duplicate" và "output không được duplicate". Bài không nói input đã được sort. Bạn cần tự sort. Sau khi sort, các phần tử bằng nhau nằm cạnh nhau — đây là sự thật cấu trúc làm cho điều kiện skip trở nên khả thi. Nếu không sort, bạn cần hash set để phát hiện duplicate ở các vị trí tùy ý, vừa tốn kém hơn vừa khó lý luận hơn.

Dải giá trị [-10, 10] đủ nhỏ để dùng frequency array enumerate subsets về mặt lý thuyết, nhưng cách đó không generalize được. Bỏ qua đi.

Approach 1: sinh tất cả rồi loại trùng

Sort mảng, enumerate tất cả 2^n tập con bằng bit manipulation, serialize mỗi tập con thành key có thể hash, và loại trùng bằng set.

class Solution:
    def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        n = len(nums)
        seen = set()
        result = []
 
        for mask in range(1 << n):
            subset = []
            for j in range(n):
                if mask & (1 << j):
                    subset.append(nums[j])
            key = tuple(subset)
            if key not in seen:
                seen.add(key)
                result.append(subset)
 
        return result

using System;
using System.Collections.Generic;
using System.Linq;
 
public class Solution {
    public IList<IList<int>> SubsetsWithDup(int[] nums) {
        Array.Sort(nums);
        int n = nums.Length;
        var seen = new HashSet<string>();
        var result = new List<IList<int>>();
 
        for (int mask = 0; mask < (1 << n); mask++) {
            var subset = new List<int>();
            for (int j = 0; j < n; j++) {
                if ((mask & (1 << j)) != 0)
                    subset.Add(nums[j]);
            }
            string key = string.Join(",", subset);
            if (seen.Add(key)) {
                result.Add(subset);
            }
        }
 
        return result;
    }
}

Phiên bản C# dùng HashSet<string> với giá trị được nối bằng dấu phẩy làm key. Điều này hoạt động vì sau khi sort, các tập con bằng nhau luôn tạo ra cùng một string. Lời gọi seen.Add(key) trả về true chỉ khi phần tử chưa tồn tại — nên if (seen.Add(key)) là cách check-and-insert gọn gàng trong một bước.

Time: O(n * 2^n) — duyệt 2^n mask, mỗi cái mất O(n) để xây dựng và serialize.

Space: O(n * 2^n) — hash set lưu đến 2^n key, mỗi key có độ dài O(n). Chi phí duplicate là thật: nếu input là [2, 2, 2], bạn sinh ra 8 tập con từ vòng bitmask nhưng chỉ 4 cái là phân biệt. Bạn tạo và hash 8 string để giữ lại 4. Khi duplicate dày đặc, lãng phí càng lớn.

Approach 2: backtracking không bao giờ sinh ra duplicate

Sort, rồi backtrack. Ở mỗi level đệ quy, trước khi chọn phần tử i, kiểm tra xem nums[i] == nums[i-1] và i > start có đúng không. Nếu cả hai đúng, bỏ qua i — nhánh bắt đầu từ nums[i] ở level này có cấu trúc giống hệt nhánh đã khám phá với nums[i-1].

class Solution:
    def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        result = []
 
        def backtrack(start: int, current: list[int]) -> None:
            result.append(current[:])
 
            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i - 1]:
                    continue
                current.append(nums[i])
                backtrack(i + 1, current)
                current.pop()
 
        backtrack(0, [])
        return result

using System;
using System.Collections.Generic;
 
public class Solution {
    public IList<IList<int>> SubsetsWithDup(int[] nums) {
        Array.Sort(nums);
        var result = new List<IList<int>>();
 
        void Backtrack(int start, List<int> current) {
            result.Add(new List<int>(current));
 
            for (int i = start; i < nums.Length; i++) {
                if (i > start && nums[i] == nums[i - 1])
                    continue;
                current.Add(nums[i]);
                Backtrack(i + 1, current);
                current.RemoveAt(current.Count - 1);
            }
        }
 
        Backtrack(0, new List<int>());
        return result;
    }
}

Time: O(n * 2^n) trong trường hợp xấu nhất (không có duplicate). Mỗi lá của cây đệ quy là một tập con phân biệt, copy nó tốn O(n). Khi có duplicate thì cây nhỏ hơn, nhưng bound không đổi vì nó được định nghĩa bởi worst-case input.

Space: O(n) cho call stack đệ quy và list current, không tính output. Độ sâu call tối đa là n. Approach 1 giữ tất cả tập con trong hash set cùng lúc; Approach 2 chỉ giữ đường đi từ gốc đến node hiện tại.

Trace tay qua nums = [1, 2, 2]

Sau khi sort: [1, 2, 2]. Hãy cùng bước qua cây backtracking. Mỗi lời gọi có dạng backtrack(start, current).

Đọc các tập con được ghi theo thứ tự: [], [1], [1,2], [1,2,2], [2], [2,2]. Sáu tập con. Khớp với output mong đợi.

Điều kiện skip kích hoạt hai lần. Ở level gốc (start=0), khi vòng lặp đến i=2, nums[2]=2 == nums[1]=2 và i=2 > start=0 — skip. Ở level [1] (start=1), khi vòng lặp đến i=2, nums[2]=2 == nums[1]=2 và i=2 > start=1 — skip. Cả hai skip đúng vì ta đã khám phá nhánh bắt đầu với nums[i-1] ở level này rồi.

Tại sao i > start chứ không phải i > 0

Đây là chỗ người ta hay nhầm. Điều kiện i > 0 and nums[i] == nums[i-1] sẽ skip phần tử i bất cứ khi nào nó bằng phần tử trước trong mảng đã sort — kể cả khi nó là phần tử đầu tiên được xem xét ở level đệ quy này. Điều đó sẽ prune sai các tập con hợp lệ.

Ví dụ cụ thể: nums = [1, 2, 2], gọi backtrack(2, [1, 2]). Ở đây start = 2. Vòng lặp bắt đầu tại i = 2, tức là nums[2] = 2 là phần tử đầu tiên được thử ở level này. Với i > 0 bạn kiểm tra nums[2] == nums[1] tức là 2 == 2 — đúng, và i > 0 là đúng — nên bạn SKIP. Nhưng i == start nên i > start là false — KHÔNG skip. Tập con [1, 2, 2] được sinh ra đúng. Nếu dùng i > 0, bạn sẽ mất [1, 2, 2] khỏi output.

Quy tắc: chỉ skip khi phần tử hiện tại tạo ra một nhánh con trùng lặp ở cùng level đệ quy — tức là một nhánh anh em (sibling branch). Một sibling trùng xảy ra khi nums[i] == nums[i-1] và i != start (tức là i > start). Điều kiện i > start chính xác là "chúng ta có đang ở phần tử đầu tiên của level này không."

Các edge case

Một phần tử (nums = [5]): backtrack(0, []) ghi [], chọn 5, gọi backtrack(1, [5]) ghi [5] và không còn phần tử nào. Output: [[], [5]]. Đúng.

Tất cả giống nhau (nums = [2, 2, 2]): sau khi sort, lần chọn đầu tiên là nums[0] = 2. Ở mỗi level tiếp theo, i > start ngăn lần xuất hiện thứ hai của 2 bắt đầu một nhánh mới ở cùng level. Cây sinh ra [], [2], [2,2], [2,2,2] — bốn tập con, đúng với power set của multiset {2,2,2}. Approach brute force sẽ sinh ra 8 bitmask combination rồi dedup còn 4.

Đã sort sẵn (nums = [1, 2, 3]): không có duplicate, điều kiện skip không bao giờ kích hoạt. Hành vi giảm về plain Subsets (78). Sort một mảng đã sort tốn O(n log n) nhưng bị dominated bởi O(n * 2^n) của backtracking.

Số âm (nums = [-1, -1, 0]): sort đặt -1, -1, 0 theo thứ tự. Skip kích hoạt cho -1 thứ hai ở level gốc. Output gồm [], [-1], [-1,-1], [-1,-1,0], [-1,0], [0]. Giá trị âm được xử lý giống hệt số dương — phép so sánh là trực tiếp.

Mảng đơn phần tử: constraint nói nums.length >= 1 nên bạn không nhận được mảng rỗng. Lệnh result.append([]) ban đầu trong phiên bản backtracking xử lý đúng n = 1 mà không cần case đặc biệt nào.

Nên dùng approach nào

Approach 2, luôn luôn. Cách hash set (Approach 1) hữu ích để có trong đầu như một "tôi luôn có thể dedup ở cuối" fallback, nhưng nó có chi phí thực: allocate O(n * 2^n) space cho string key, serialize mỗi tập con kể cả những cái sẽ bị loại bỏ, và không compose gọn gàng vào phần còn lại của backtracking family. Khi bạn gặp Combination Sum II (40) hay Permutations II (47), bạn sẽ dùng cùng điều kiện skip — và nếu bạn chỉ học cách hash set ở đây, bạn sẽ phải re-derive nó từ đầu.

Approach 2 cũng có một invariant sạch hơn để lý luận: sau khi sort, cây đệ quy chính xác là cây của các tập con phân biệt, không hơn không kém. Bạn không phải trả chi phí sinh thêm rồi bỏ đi.

Sự khác biệt O(n) space cho call stack so với O(n * 2^n) cho hash set không phải lý thuyết — ở n = 10 với duplicate dày đặc như [1,1,1,1,1,1,1,1,1,1], brute force xây dựng 1024 string key để giữ 11 tập con. Approach 2 xây dựng và ghi đúng 11 cái.

Bảng so sánh

Cả hai có cùng time class. Khác biệt về space là lý do để dùng Approach 2, và khả năng generalize mới là lý do mạnh hơn.

Pattern có thể chuyển giao và hướng tiếp theo

Pattern cốt lõi là level-wise duplicate pruning trên input đã sort trong backtracking. Sorting gom các phần tử bằng nhau lại gần nhau. Ở mỗi level đệ quy, bạn cho phép lần xuất hiện đầu tiên của mỗi giá trị và skip các lần tiếp theo (i > start and nums[i] == nums[i-1]). Điều này ngăn các subtree trùng nhau bị khám phá. Insight cấu trúc cốt lõi: hai nhánh ở cùng level đều bắt đầu với cùng giá trị sẽ tạo ra các subtree giống hệt nhau, nên chỉ cần khám phá nhánh đầu tiên là đủ và đúng.

Pattern này xuất hiện trong ít nhất ba bài khác trong series:

Combination Sum II (40) — tìm tất cả combination unique có tổng bằng target, từ input có thể có duplicate. Điều kiện skip hoàn toàn giống, yêu cầu sort-first hoàn toàn giống. Thay đổi duy nhất so với Subsets II là bạn dừng đệ quy khi tổng đang chạy vượt quá target thay vì thu thập mọi prefix. Nếu đã thoải mái ở đây, hãy đến đó tiếp.

Permutations II (47) — tất cả permutation unique của input có thể có duplicate. Logic skip tương tự nhưng cấu trúc khác: bạn không thể dùng index start (permutation cho phép mọi vị trí), nên thường dùng mảng boolean used[] và skip nums[i] == nums[i-1] and not used[i-1]. Cùng ý tưởng "sibling bằng nhau ở cùng level -> skip", được implement khác vì permutation không có vị trí bắt đầu cố định.

Subsets (78) — bài trước bài này trong series. Không có duplicate, không cần skip. Nếu Subsets II còn chưa chắc, hãy quay lại 78 trước và đảm bảo template backtracking vững chắc rồi mới thêm điều kiện skip.

Combination Sum III (216) — chọn k số từ 1-9 có tổng bằng n. Không có duplicate trong input, nhưng constraint về số lượng k thêm một điều kiện pruning mới. Bài tốt để luyện constraint-based pruning sau khi đã rõ về duplicate case.

Subsets II ở vị trí thứ 6 trong backtracking series — sau các bài subset và combination-sum thuần túy, trước các bài đòi hỏi state phức tạp hơn. Đây là bài làm cho pattern duplicate-skipping trở nên tường minh và cho nó một chỗ đứng rõ ràng. Khi bạn có thể giải thích chính xác tại sao i > start chứ không phải i > 0, phần còn lại của các bài duplicate-backtracking trở thành các biến thể.