Combination Sum: backtracking với việc dùng lại phần tử

Bài trước trong series này, Subsets, đưa ra quyết định nhị phân tại mỗi phần tử: chọn hoặc bỏ qua. Đơn giản và không có điều kiện ràng buộc. Combination Sum thêm vào hai thứ cùng lúc — một ràng buộc về tổng, và khả năng dùng lại bất kỳ phần tử nào bao nhiêu lần cũng được. Chính quy tắc thứ hai khiến nhiều người vấp ngã. Nghe có vẻ như nó làm bài toán khó hơn, nhưng nếu xử lý đúng cách thì thực ra nó đơn giản hóa việc tránh các tổ hợp trùng lặp.

LeetCode 39: cho một mảng các số nguyên phân biệt và một giá trị target, tìm tất cả các tổ hợp duy nhất có tổng bằng target. Bạn được dùng mỗi phần tử bao nhiêu lần tùy thích. Đề bài đảm bảo có không quá 150 tổ hợp hợp lệ cho các test case đã cho.

Constraints nói lên điều gì

1 <= candidates.length <= 30. Ba mươi phần tử. Kết hợp với 1 <= target <= 40 và 2 <= candidates[i] <= 40, không gian tìm kiếm bị giới hạn chặt chẽ. Giá trị nhỏ nhất là 2, nghĩa là độ sâu tối đa của bất kỳ tổ hợp nào là target / 2 = 20 tầng (khi bạn liên tục chọn 2 để đạt 40). Branching factor tối đa là 30, nhưng pruning cắt giảm đáng kể trong thực tế. Đây là chế độ mà backtracking phù hợp nhất — không phải DP, không phải BFS, mà backtracking.

2 <= candidates[i] <= 40. Không có số 0, không có số âm. Đây là ràng buộc quan trọng. Nếu candidates có thể chứa số 1, một tổ hợp với target = 40 có thể sâu đến 40 tầng (toàn số 1). Ràng buộc candidates[i] >= 2 giới hạn độ sâu tại target / min(candidates). Tệ nhất là 40 / 2 = 20, hoàn toàn ổn.

Tất cả phần tử đều phân biệt. Điều này có nghĩa là nguồn duy nhất tạo ra các tổ hợp trùng lặp là thứ tự tìm kiếm, không phải input. Bạn không cần dedup sau khi có kết quả. Bạn chỉ cần đảm bảo bản thân quá trình tìm kiếm không sinh ra [2, 3] và [3, 2] như hai đáp án riêng biệt.

Brute force: điều gì xảy ra khi không kiểm soát index

Cách tiếp cận ngây thơ: tại mỗi lần gọi đệ quy, thử mọi phần tử trong candidates từ đầu. Duy trì tổng đang chạy; khi bằng target thì ghi lại một bản sao. Khi vượt quá target thì dừng.

class Solution:
    def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
        result = []
 
        def backtrack(current: list[int], remaining: int) -> None:
            if remaining == 0:
                result.append(current[:])
                return
            if remaining < 0:
                return
            for num in candidates:
                current.append(num)
                backtrack(current, remaining - num)
                current.pop()
 
        backtrack([], target)
        return result

public class Solution {
    public IList<IList<int>> CombinationSum(int[] candidates, int target) {
        var result = new List<IList<int>>();
 
        void Backtrack(List<int> current, int remaining) {
            if (remaining == 0) {
                result.Add(new List<int>(current));
                return;
            }
            if (remaining < 0) return;
            foreach (int num in candidates) {
                current.Add(num);
                Backtrack(current, remaining - num);
                current.RemoveAt(current.Count - 1);
            }
        }
 
        Backtrack(new List<int>(), target);
        return result;
    }
}

Code này đúng theo nghĩa tìm được các tổ hợp hợp lệ. Nhưng nó không đúng theo nghĩa trả về các tổ hợp duy nhất. Với candidates = [2, 3], target = 5, nó sinh ra cả [2, 3] lẫn [3, 2]. Bài toán nói rõ hai tổ hợp này là một — vì chúng chứa cùng một multiset, chỉ tần suất quan trọng, không phải thứ tự.

Cách fix là kiểm soát phần tử nào lần gọi đệ quy được phép xét. Bạn có thể sort kết quả rồi loại trùng, nhưng đó là làm thêm việc trên một không gian tìm kiếm đã thừa. Cách thực sự đúng là ngăn không cho chúng được sinh ra ngay từ đầu.

Time: O(N^(T/M)) với N là số candidates, T là target, M là giá trị nhỏ nhất trong candidates. Space: O(T/M) cho call stack. Độ sâu bị giới hạn bởi số lần bạn có thể trừ giá trị nhỏ nhất từ target trước khi thành âm.

Tôi sẽ không dùng cái này. Vấn đề duplicate tự loại nó khỏi danh sách. Tôi đưa nó vào đây vì đây là cách hầu hết mọi người thử đầu tiên, và hiểu tại sao nó thất bại giúp cho giải pháp tiếp theo trở nên hiển nhiên.

Backtracking tối ưu: sắp xếp và prune

Insight cốt lõi rất đơn giản. Nếu bạn xử lý candidates theo thứ tự và mỗi lần gọi đệ quy chỉ xét các phần tử tại vị trí hiện tại trở về sau, bạn không thể bao giờ sinh ra [3, 2] sau khi đã sinh ra [2, 3]. Index hoạt động như một cánh cửa một chiều: bạn tiến về phía trước, không bao giờ lùi.

Sắp xếp mảng trước cho phép một cải tiến thứ hai: dừng sớm. Nếu candidates[i] > remaining, thì candidates[i+1], candidates[i+2], và mọi thứ sau đó cũng lớn hơn (mảng đã sắp xếp). Bạn có thể break vòng lặp thay vì tiếp tục đệ quy vào những nhánh chắc chắn thất bại.

class Solution:
    def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
        candidates.sort()
        result = []
 
        def backtrack(start: int, current: list[int], remaining: int) -> None:
            if remaining == 0:
                result.append(current[:])
                return
            for i in range(start, len(candidates)):
                if candidates[i] > remaining:
                    break  # đã sắp xếp — mọi thứ sau cũng quá lớn
                current.append(candidates[i])
                backtrack(i, current, remaining - candidates[i])  # i, không phải i+1 — cho phép dùng lại
                current.pop()
 
        backtrack(0, [], target)
        return result

public class Solution {
    public IList<IList<int>> CombinationSum(int[] candidates, int target) {
        Array.Sort(candidates);
        var result = new List<IList<int>>();
 
        void Backtrack(int start, List<int> current, int remaining) {
            if (remaining == 0) {
                result.Add(new List<int>(current));
                return;
            }
            for (int i = start; i < candidates.Length; i++) {
                if (candidates[i] > remaining) break;
                current.Add(candidates[i]);
                Backtrack(i, current, remaining - candidates[i]);  // i, không phải i+1
                current.RemoveAt(current.Count - 1);
            }
        }
 
        Backtrack(0, new List<int>(), target);
        return result;
    }
}

Chi tiết quan trọng nhất là truyền i trở lại vào lần gọi đệ quy, không phải i + 1. Trong Subsets, lần gọi đệ quy tiến index thêm 1 vì mỗi phần tử xuất hiện tối đa một lần. Ở đây bạn truyền i lại — điều này cho phép cùng một phần tử được chọn nhiều lần, đúng với yêu cầu của bài toán. Tính chất monotone-index vẫn giữ: các lần gọi tương lai chỉ được chọn phần tử tại vị trí i trở về sau, ngăn không cho [3, 2] được sinh ra.

Truy vết qua ví dụ

candidates = [2, 3, 6, 7], target = 7. Sau khi sắp xếp: [2, 3, 6, 7].

Cây kết thúc tại hai lá hợp lệ: [2, 2, 3] và [7]. Chú ý nhánh [3] hầu như không phát triển — khi remaining giảm xuống 1, mọi candidate (tối thiểu 2) đều thất bại ngay điều kiện > remaining và break. Đó là pruning đang hoạt động.

Theo từng bước cho đường dẫn [2, 2, 3]:

backtrack(start=0, current=[], remaining=7)
  chọn candidates[0]=2 → current=[2], remaining=5
  backtrack(start=0, current=[2], remaining=5)
    chọn candidates[0]=2 → current=[2,2], remaining=3
    backtrack(start=0, current=[2,2], remaining=3)
      chọn candidates[0]=2 → current=[2,2,2], remaining=1
      backtrack(start=0, current=[2,2,2], remaining=1)
        candidates[0]=2 > 1 → break
      pop 2 → current=[2,2]
      chọn candidates[1]=3 → current=[2,2,3], remaining=0
      backtrack(start=1, current=[2,2,3], remaining=0)
        remaining==0 → ghi lại [2,2,3]  ← ĐÃ TÌM THẤY
      pop 3 → current=[2,2]
      candidates[2]=6 > 3 → break
    pop 2 → current=[2]
    ...

Bản sao current[:] (Python) hoặc new List<int>(current) (C#) tại lá là bắt buộc. Không có nó, mọi entry trong result sẽ trỏ đến cùng một list, và bạn sẽ thấy tất cả các entry hiển thị trạng thái cuối cùng của current sau khi backtracking hoàn thành — thường là rỗng.

Các edge case

Không có tổ hợp hợp lệ (candidates = [2], target = 1): candidates[0] = 2 > 1, vòng lặp break ngay lần đầu tiên. Kết quả rỗng. Code xử lý điều này mà không cần trường hợp đặc biệt.

Phần tử duy nhất bằng target (candidates = [7], target = 7): candidates[0] = 7, remaining = 7. Bằng nhau, không lớn hơn, nên bạn chọn nó. remaining - 7 = 0, base case kích hoạt, [7] được ghi lại. Đúng.

Tất cả candidates vượt target (candidates = [5, 6, 7], target = 3): sau khi sắp xếp, candidates[0] = 5 > 3. Lần lặp đầu tiên của vòng lặp break. Kết quả rỗng. Lại một lần nữa không cần trường hợp đặc biệt — điều kiện pruning xử lý rồi.

Target chia hết cho minimum (candidates = [2, 3, 6, 7], target = 6): sinh ra [2, 2, 2], [3, 3], và [6]. Cả ba đường dẫn kết thúc đúng. Độ sâu đạt 3 cho [2, 2, 2] (đường sâu nhất tại 6/2=3 bước), hoàn toàn nằm trong giới hạn call stack.

So sánh hai cách tiếp cận

Giới hạn asymptotic trong trường hợp tệ nhất là như nhau — bạn vẫn khám phá một cây có độ sâu T/M với tối đa N nhánh mỗi node. Nhưng trong thực tế phiên bản sắp xếp với pruning ghé thăm ít node hơn nhiều. Với ví dụ điển hình [2, 3, 6, 7] target 7, brute force khám phá các đường bắt đầu bằng [7, 2] và [6, 3] trước khi nhận ra chúng vượt quá, rồi cũng khám phá [2, 7] và [3, 6] như những đường hoàn toàn riêng biệt. Phiên bản sắp xếp không bao giờ đi ngược: khi chọn 6 ở độ sâu 1 và thấy remaining = 1 < 2, nó break và bỏ qua 7 hoàn toàn. Tiết kiệm hằng số thực sự có ý nghĩa, dù ký hiệu big-O che giấu điều đó.

Space: O(T/M) cho độ sâu đệ quy, cộng thêm O(k * S) trong đó k là số tổ hợp hợp lệ và S là độ dài trung bình mỗi tổ hợp — đó là chi phí output. Bạn không thể giảm chi phí output; bạn phải lưu trữ những gì bài toán yêu cầu.

Vị trí trong series backtracking

Subsets là điểm khởi đầu: binary include/exclude, không có ràng buộc, không pruning. Combination Sum thêm hai thứ — ràng buộc tổng và dùng lại phần tử — và cả hai đều xuất phát tự nhiên từ cùng một skeleton backtracking. Index start làm ba việc ở đây: ngăn trùng lặp, cho phép dùng lại (bằng cách truyền i chứ không phải i+1), và kết hợp với sắp xếp thì cho phép dừng sớm.

Từ đây, các bài tiếp theo phù hợp là:

• Combination Sum II (LeetCode 40): cùng cấu trúc nhưng mỗi phần tử chỉ dùng được một lần, và input có thể có trùng lặp. Index start tiến thêm lên i+1, và bạn thêm guard bỏ qua: nếu candidates[i] == candidates[i-1] và i > start, bỏ qua để tránh tổ hợp trùng. Một điều kiện thêm; cùng skeleton.
• Combination Sum III (LeetCode 216): tìm tất cả tổ hợp đúng k số từ 1 đến 9 có tổng bằng n. Hai base case thay vì một — bạn kiểm tra cả count lẫn sum. Prune sớm khi count vượt k.
• Word Search (LeetCode 79): backtracking trong không gian 2D. Thay vì index tuyến tính kiểm soát phần tử nào được xét tiếp, bạn dùng visited grid. Bước undo đánh dấu một ô là chưa thăm. Cùng ý tưởng, hình học khác.
• Letter Combinations of a Phone Number (LeetCode 17): tại mỗi vị trí bạn chọn một ký tự từ một tập cố định. Không dùng lại qua các vị trí, không có ràng buộc tổng — nhưng skeleton hoàn toàn giống: vòng lặp qua các lựa chọn, đệ quy, undo.