Combination Sum II: khi phần tử trùng trong input tạo ra tổ hợp trùng trong output

Combination Sum (LeetCode 39) cho phép reuse phần tử thoải mái — vấn đề duy nhất là ngăn duplicate theo thứ tự hoán vị, giải quyết bằng cách ép forward-only index. Combination Sum II lấy đi quyền reuse và đưa cho bạn một input bẩn hơn: mảng candidates có thể chứa giá trị lặp, mỗi phần tử chỉ dùng được đúng một lần, và kết quả vẫn phải là tập các tổ hợp duy nhất. Sự kết hợp của hai ràng buộc này — không reuse, input có thể lặp — khiến việc tránh duplicate trở nên khó hơn theo một cách rất cụ thể.

Cốt lõi của khó khăn là thế này: nếu candidates chứa [1, 1, 2] và target là 3, cả số 1 thứ nhất lẫn số 1 thứ hai đều có thể là điểm khởi đầu cho [1, 2] hợp lệ. Nếu không có guard nào, cây backtracking sẽ tìm ra [1, 2] hai lần — một lần bắt đầu từ index 0 và một lần từ index 1. Hai vị trí khác nhau trong mảng, nhưng tổ hợp về mặt ngữ nghĩa là giống hệt nhau. Bài toán yêu cầu loại bỏ duplicate đó.

Đề bài

Cho một mảng số nguyên candidates (có thể chứa phần tử trùng lặp) và một số nguyên target, tìm tất cả các tổ hợp duy nhất trong candidates sao cho tổng bằng target. Mỗi số chỉ được dùng đúng một lần, và tập kết quả không được chứa các tổ hợp trùng nhau. Full statement: LeetCode 40.

Ràng buộc:
- 1 <= candidates.length <= 100
- 1 <= candidates[i] <= 50
- 1 <= target <= 30

Constraints đang nói gì với bạn

1 <= candidates.length <= 100. Một trăm phần tử. Lớn hơn con số 30 của LeetCode 39, nhưng backtracking vẫn phù hợp — recursion lưu trạng thái không bao giờ vật chất hóa toàn bộ cây 2^100 vì pruning, và target <= 30 mới là giới hạn ràng buộc độ sâu. Recursion có thể đi sâu tối đa 30 tầng (chọn 30 số 1), và với tối đa 100 nhánh mỗi tầng (trước pruning), cái này hoàn toàn trong ngân sách.

1 <= candidates[i] <= 50. Tất cả đều dương. Đây là điều quan trọng: không có số 0 hay số âm cần lo, nghĩa là mỗi phần tử bạn thêm vào tổ hợp hiện tại kéo remaining target xuống một cách nghiêm ngặt. Nhánh remaining < 0 trở nên không thể đạt đến nếu bạn prune với candidates[i] > remaining — khi điều kiện đó kích hoạt, bạn có thể break ngay vì mảng đã sort đảm bảo mọi thứ phía sau còn lớn hơn.

1 <= target <= 30. Target tối đa 30, và mỗi phần tử ít nhất 1, nên độ sâu tổ hợp tối đa là 30. Điều đó ràng buộc call stack ngay cả trong trường hợp xấu nhất.

Sự hiện diện của duplicate trong candidates không được nêu trong bảng constraints nhưng được thiết lập qua ví dụ: [10,1,2,7,6,1,5] chứa hai số 1. Ràng buộc candidates[i] >= 1 nghĩa là chúng ta không thể dùng tính duy nhất của giá trị làm proxy cho tính duy nhất của vị trí. Điều này buộc phải xử lý duplicate rõ ràng ở tầng lựa chọn, không chỉ ở tầng kết quả.

Approach 1: backtracking với hash set để deduplicate kết quả

Ý tưởng đơn giản nhất: chạy backtracking thoải mái, sau đó deduplicate khi ra. Ở mỗi bước, include hoặc exclude phần tử hiện tại. Khi remaining == 0, sort tổ hợp và thêm vào set. Bước sorting chuẩn hóa thứ tự để [1, 2] tìm qua index 0 và [1, 2] tìm qua index 1 va chạm trong set và chỉ còn một bản.

class Solution:
    def combinationSum2(self, candidates: list[int], target: int) -> list[list[int]]:
        result_set: set[tuple[int, ...]] = set()
 
        def backtrack(index: int, current: list[int], remaining: int) -> None:
            if remaining == 0:
                result_set.add(tuple(sorted(current)))
                return
            if remaining < 0 or index >= len(candidates):
                return
            # bỏ qua phần tử hiện tại
            backtrack(index + 1, current, remaining)
            # chọn phần tử hiện tại
            current.append(candidates[index])
            backtrack(index + 1, current, remaining - candidates[index])
            current.pop()
 
        backtrack(0, [], target)
        return [list(combo) for combo in result_set]

using System.Collections.Generic;
using System.Linq;
 
public class Solution {
    public IList<IList<int>> CombinationSum2(int[] candidates, int target) {
        var resultSet = new HashSet<string>();
        var finalResult = new List<IList<int>>();
 
        Backtrack(0, new List<int>(), target, candidates, resultSet);
 
        foreach (var key in resultSet) {
            finalResult.Add(key.Split(',').Select(int.Parse).ToList());
        }
        return finalResult;
    }
 
    private void Backtrack(int index, List<int> current, int remaining,
                           int[] candidates, HashSet<string> resultSet) {
        if (remaining == 0) {
            var sorted = current.OrderBy(x => x).ToList();
            resultSet.Add(string.Join(",", sorted));
            return;
        }
        if (remaining < 0 || index >= candidates.Length) return;
 
        // exclude
        Backtrack(index + 1, current, remaining, candidates, resultSet);
        // include
        current.Add(candidates[index]);
        Backtrack(index + 1, current, remaining - candidates[index], candidates, resultSet);
        current.RemoveAt(current.Count - 1);
    }
}

Cách này hoạt động, nhưng lãng phí theo hai nghĩa. Thứ nhất, nó khám phá toàn bộ cây 2^n — cây quyết định include/exclude đầy đủ — mà không prune các nhánh đã vượt quá target. Thứ hai, nó sort và hash mọi tổ hợp hợp lệ tìm được, trả O(k log k) mỗi tổ hợp với k là độ dài. Nếu input có nhiều giá trị lặp, nhiều nhánh sẽ hội tụ về cùng một tổ hợp, lãng phí tất cả công sức trước khi va chạm trong set.

Time: O(2^n * n log n) — 2^n node được khám phá, với overhead sort O(n log n) mỗi tổ hợp tìm được.

Space: O(2^n * n) — hash set có thể tích lũy tất cả các tổ hợp phân biệt, mỗi cái được lưu dưới dạng chuỗi tối đa n phần tử.

Tôi sẽ không ship cái này. Đây là lần thử đầu tiên đúng để xác định điều cần sửa, nhưng tạo ra duplicate rồi deduplicate thì tệ hơn hẳn so với không tạo ra chúng ngay từ đầu.

Approach 2: sorted backtracking với skip guard cùng level

Cách sửa là deduplicate trong quá trình tìm kiếm, không phải sau đó. Sort mảng candidates trước. Bây giờ tất cả giá trị bằng nhau nằm kề nhau. Khi lặp qua các lựa chọn ở một tầng recursion nhất định, nếu bạn gặp một giá trị giống với giá trị bạn vừa thử ở tầng này, hãy bỏ qua — bạn đã khám phá nhánh đó rồi.

Điều kiện là i > start and candidates[i] == candidates[i-1]. Phần i > start mới là nửa không rõ ràng. Nó đảm bảo bạn chỉ skip một giá trị khi nó là lần lặp ở tầng hiện tại. Ở các tầng khác nhau, cùng một giá trị có thể xuất hiện vì lý do khác — số 1 thứ nhất trong [1, 1, 6] đến từ một tầng, số 1 thứ hai từ tầng dưới. Bạn không thể skip dựa trên i > 0 một mình, vì điều đó sẽ chặn số 1 thứ hai ngay cả khi nó đang được xét cho vị trí tiếp theo trong tổ hợp, không phải cùng vị trí.

class Solution:
    def combinationSum2(self, candidates: list[int], target: int) -> list[list[int]]:
        candidates.sort()
        result: list[list[int]] = []
 
        def backtrack(start: int, current: list[int], remaining: int) -> None:
            if remaining == 0:
                result.append(current[:])
                return
            for i in range(start, len(candidates)):
                # skip giá trị lặp ở cùng tầng recursion
                if i > start and candidates[i] == candidates[i - 1]:
                    continue
                # prune: mảng đã sort nên mọi thứ sau cũng quá lớn
                if candidates[i] > remaining:
                    break
                current.append(candidates[i])
                backtrack(i + 1, current, remaining - candidates[i])
                current.pop()
 
        backtrack(0, [], target)
        return result

using System;
using System.Collections.Generic;
 
public class Solution {
    public IList<IList<int>> CombinationSum2(int[] candidates, int target) {
        Array.Sort(candidates);
        var result = new List<IList<int>>();
        Backtrack(0, new List<int>(), target, candidates, result);
        return result;
    }
 
    private void Backtrack(int start, List<int> current, int remaining,
                           int[] candidates, IList<IList<int>> result) {
        if (remaining == 0) {
            result.Add(new List<int>(current));
            return;
        }
        for (int i = start; i < candidates.Length; i++) {
            // skip giá trị lặp ở cùng tầng recursion
            if (i > start && candidates[i] == candidates[i - 1]) continue;
            // prune
            if (candidates[i] > remaining) break;
 
            current.Add(candidates[i]);
            Backtrack(i + 1, current, remaining - candidates[i], candidates, result);
            current.RemoveAt(current.Count - 1);
        }
    }
}

Lưu ý i + 1 trong lời gọi recursive, không phải i. Sự khác biệt nhỏ đó so với LeetCode 39 là điều ép "mỗi phần tử dùng tối đa một lần." Trong LeetCode 39 bạn truyền i để cho phép reuse. Ở đây bạn truyền i + 1 để tiêu thụ vị trí hiện tại và di chuyển tiếp.

Time: O(2^n) trong trường hợp xấu nhất (không có pruning nào kích hoạt, không có duplicate để skip), nhưng skip guard loại bỏ toàn bộ nhánh khi input có giá trị lặp. Thời gian chạy thực tế trên input nhiều duplicate tốt hơn đáng kể so với phiên bản brute force.

Space: O(target) cho recursion stack — tối đa target tầng sâu vì mỗi phần tử ít nhất là 1. Chi phí output là O(k * S) với k là số tổ hợp hợp lệ và S là độ dài tổ hợp trung bình, nhưng cái đó không thể tránh khỏi.

Trace tay qua ví dụ chính

candidates = [10, 1, 2, 7, 6, 1, 5], target = 8.

Sau khi sort: [1, 1, 2, 5, 6, 7, 10]. Indices: 0=1, 1=1, 2=2, 3=5, 4=6, 5=7, 6=10.

Bốn tổ hợp hợp lệ tìm được: [1, 1, 6], [1, 2, 5], [1, 7], [2, 6]. Khớp với output mong đợi.

Chú ý rằng ở root level, index 1 (giá trị 1) bị skip vì candidates[1] == candidates[0] và i > start (1 > 0). Đó là skip guard đang hoạt động: chúng ta đã khám phá nhánh bắt đầu từ số 1 thứ nhất rồi; bắt đầu từ số 1 thứ hai sẽ tạo ra cùng subtree đó. Toàn bộ subtree gốc tại [1] (lần thứ hai) không bao giờ được thăm.

Bên trong subtree [1] (bắt đầu từ index 0), số 1 thứ hai ở index 1 không bị skip — vì bây giờ i = 1 và start = 1, nên i > start là false. Số 1 thứ hai là lựa chọn hợp lệ cho vị trí thứ hai của tổ hợp, đó là cách [1, 1, 6] được tìm ra.

Sự bất đối xứng đó — cùng giá trị, xử lý khác nhau tùy thuộc vào i > start — là toàn bộ chiêu.

Các edge case dễ nhầm

Không có tổ hợp hợp lệ (candidates = [5, 6, 7], target = 3): sau khi sort, candidates[0] = 5 > 3, nên vòng lặp break ngay ở lần gọi đầu tiên. Kết quả rỗng mà không cần xử lý đặc biệt.

Tất cả phần tử giống nhau (candidates = [2, 2, 2, 2], target = 4): sau khi sort, [2, 2, 2, 2]. Ở root level, chỉ index 0 được thử (index 1, 2, 3 đều bị skip bởi duplicate guard). Từ [2], vòng lặp bắt đầu từ index 1 — candidates[1] = 2, và 1 > 1 là false nên không bị skip. [2, 2] được tìm thấy và remaining = 4 - 2 - 2 = 0 — kết quả là [[2, 2]]. Đúng.

Một phần tử duy nhất bằng target (candidates = [8], target = 8): ghi nhận [8] ngay lập tức. Một lần gọi backtrack, một leaf. Sạch.

Duplicate nhưng chỉ dùng được một (candidates = [1, 1], target = 1): ở root, pick index 0 (giá trị 1), remaining về 0, ghi nhận [1]. Quay lại root, index 1 bị skip (duplicate cùng level). Kết quả: [[1]]. Số 1 thứ hai bị loại đúng cách khỏi việc trở thành một nhánh riêng dẫn đến cùng output.

Target nhỏ hơn phần tử nhỏ nhất (candidates = [3, 4, 5], target = 2): phần tử đầu tiên đã vượt quá remaining, break kích hoạt ngay. Kết quả rỗng.

Quên copy list — không phải edge case liên quan đến constraint nhưng là lỗi phổ biến: result.append(current) lưu reference vào list đang sống. Sau khi backtracking hoàn thành, list đó rỗng. Luôn dùng current[:] trong Python hoặc new List<int>(current) trong C#.

Approach nào thực tế

Approach 2, mọi lúc. Không phải quyết định khó.

Approach hash set (Approach 1) tạo ra các nhánh duplicate rồi trả tiền để sort và hash chúng đi. Tính toán bị lãng phí ngay từ khoảnh khắc nhánh duplicate bắt đầu. Approach 2 loại bỏ những nhánh đó trước khi chúng tồn tại — skip guard kích hoạt ở tầng vòng lặp, nên subtree bị lặp không bao giờ được vào. Kết quả như nhau; công sức thì không.

Có một cám dỗ chọn Approach 1 vì logic dễ lý luận hơn: "chỉ cần tìm tất cả rồi deduplicate." Lý luận đó hoạt động trong các bài mà duplicate trong output hiếm. Ở đây chúng mang tính cấu trúc — mỗi giá trị lặp trong input gây ra các nhánh duplicate — và chi phí tăng theo kích thước của subtree bị lặp. Skip guard không phải tối ưu hóa; đó là cách bài toán được giải đúng.

Trường hợp duy nhất tôi cân nhắc lại: bạn đang trong một cuộc thi với 5 phút còn lại. Phiên bản hash set nhanh hơn để gõ và rõ ràng là đúng. Trong một code review thực tế, phiên bản sorted là cái tôi sẽ merge.

Bảng so sánh

Vị trí trong series backtracking

Combination Sum (LeetCode 39) thiết lập skeleton backtracking cốt lõi cho các bài combination: sort, start index, remaining, break khi overshoot. Combination Sum II là skeleton đó với hai thay đổi: i + 1 thay vì i trong lời gọi recursive (không reuse), và skip guard (xử lý input duplicate). Cộng lại hai thay đổi đó là toàn bộ diff. Phần còn lại của bài là giải thích tại sao chúng hoạt động.

Một vài bài tiếp theo tự nhiên từ đây:

Combination Sum III (LeetCode 216) thêm một ràng buộc thứ hai bên cạnh tổng: bạn phải dùng đúng k số, lấy từ 1 đến 9, mỗi số tối đa một lần. Cấu trúc backtracking giống nhau — start index, pruning, không reuse — nhưng bạn theo dõi cả count lẫn sum trong base case. Input không có duplicate (1–9 đều phân biệt), nên skip guard không cần thiết.

Subsets II (LeetCode 90) là phiên bản subset trực tiếp của bài này. Thay vì hướng đến một tổng cụ thể, tìm tất cả các subset duy nhất của một mảng có thể chứa duplicate. Skip guard hoàn toàn giống nhau: i > start and candidates[i] == candidates[i-1]. Cùng pattern, không có ràng buộc tổng.

Letter Combinations of a Phone Number (LeetCode 17) trông cấu trúc khác nhưng dùng cùng skeleton loop-over-choices-then-recurse. Thay vì skip guard cho duplicate, "lựa chọn" ở mỗi level được định nghĩa bởi bảng ánh xạ bàn phím điện thoại. Không cần deduplication; cấu trúc xử lý nó theo cách xây dựng.

Palindrome Partitioning (LeetCode 131) đưa backtracking vào không gian chuỗi. Ở mỗi vị trí bạn quyết định cắt ở đâu, thu thập prefix nếu nó là palindrome, và recurse trên suffix. Hình dạng cây khác, nhưng skeleton push-recurse-pop hoàn toàn giống nhau. Không cần skip guard vì các điểm cắt là theo vị trí, không phải theo giá trị.