05. Combination Sum Problems

📌 05. Combination Sum Problems

5.1 Bài toán

Cho một mảng candidates và một giá trị target, tìm tất cả các tổ hợp các phần tử trong mảng sao cho tổng bằng target.

Có nhiều biến thể:

• Combination Sum I: Mỗi phần tử được dùng không giới hạn số lần
• Combination Sum II: Mỗi phần tử dùng tối đa 1 lần, mảng có thể có duplicate
• Combination Sum III: Chọn k số từ 1-9, tổng = n

5.2 Ví von thực tế: Trả tiền thừa

Bạn là thu ngân, cần trả lại cho khách đúng target đồng, và bạn có các loại tiền mệnh giá candidates. Bạn cần tìm tất cả cách trả tiền thừa.

Ví dụ: target = 7, candidates = [2, 3, 5]

• 2 + 2 + 3 = 7
• 2 + 5 = 7
• 3 + 2 + 2 = 7? Không! Vì [2,2,3] và [3,2,2] là cùng một tổ hợp.

Vậy mình cần tránh đếm trùng bằng cách luôn chọn phần tử theo thứ tự không giảm.

5.3 Combination Sum I — Thuật toán chi tiết

Ý tưởng: Ở mỗi bước, ta chọn một phần tử (có thể chọn lại), trừ vào target. Khi target = 0 → tìm được tổ hợp. Khi target < 0 → backtrack.

Quan trọng: Để tránh duplicate, khi đệ quy ta chỉ xét phần tử từ vị trí start trở đi (không quay lại phần tử trước).

target=7, start=0, current=[]Chọn 2, target=5Chọn 3, target=4Chọn 5, target=2Chọn 2, target=3Chọn 3, target=2Chọn 5, target=0 ✓ [2,5]Chọn 2, target=1Chọn 3, target=0 ✓ [2,2,3]Chọn 2, target=-1 ✗Chọn 3, target=-2 ✗Chọn 3, target=1Chọn 5, target=-1 ✗Chọn 5, target=-3 ✗Chọn 3, target=-2 ✗Chọn 3, target=-1 ✗

5.4 Mô phỏng từng bước

candidates = [2, 3, 5], target = 7

backtrack(start=0, current=[], remaining=7)
│
├── Chọn 2 (start=0): remaining=5, current=[2]
│   ├── Chọn 2 (start=0): remaining=3, current=[2,2]
│   │   ├── Chọn 2 (start=0): remaining=1, current=[2,2,2]
│   │   │   ├── Chọn 2: remaining=-1 < 0 → BACKTRACK
│   │   │   ├── Chọn 3: remaining=-2 < 0 → BACKTRACK
│   │   │   └── Chọn 5: remaining=-4 < 0 → BACKTRACK
│   │   │   (Quay lại, bỏ 2, current=[2,2])
│   │   │
│   │   ├── Chọn 3 (start=1): remaining=0 → FOUND! [2,2,3] ✓
│   │   └── Chọn 5 (start=2): remaining=-2 < 0 → BACKTRACK
│   │   (Quay lại, bỏ 2, current=[2])
│   │
│   ├── Chọn 3 (start=1): remaining=2, current=[2,3]
│   │   ├── Chọn 3: remaining=-1 → BACKTRACK
│   │   └── Chọn 5: remaining=-3 → BACKTRACK
│   │
│   └── Chọn 5 (start=2): remaining=0 → FOUND! [2,5] ✓
│
├── Chọn 3 (start=1): remaining=4, current=[3]
│   ├── Chọn 3: remaining=1, current=[3,3]
│   │   ├── Chọn 3: remaining=-2 → BACKTRACK
│   │   └── Chọn 5: remaining=-4 → BACKTRACK
│   └── Chọn 5: remaining=-1 → BACKTRACK
│
└── Chọn 5 (start=2): remaining=2, current=[5]
    └── Chọn 5: remaining=-3 → BACKTRACK

Kết quả: [[2,2,3], [2,5]]

5.5 Code — Combination Sum I

Python:

def combination_sum(candidates, target):
    result = []
    candidates.sort()  # Sort để pruning
 
    def backtrack(start, current, remaining):
        # Base case: tìm được tổ hợp
        if remaining == 0:
            result.append(current[:])
            return
 
        for i in range(start, len(candidates)):
            # Pruning: nếu candidates[i] > remaining,
            # thì các phần tử sau cũng > remaining (đã sort)
            if candidates[i] > remaining:
                break
 
            current.append(candidates[i])
            # Chú ý: start = i (không phải i+1) vì được chọn lại
            backtrack(i, current, remaining - candidates[i])
            current.pop()  # Backtrack
 
    backtrack(0, [], target)
    return result
 
print(combination_sum([2, 3, 5], 7))
# [[2, 2, 3], [2, 5]]

Python (class style - giống format LeetCode):

from typing import List
 
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        candidates.sort()  # Sort để pruning hiệu quả
 
        def backtrack(start: int, current: List[int], remaining: int):
            # Base case: tìm được tổ hợp có tổng = target
            if remaining == 0:
                result.append(current[:])
                return
 
            for i in range(start, len(candidates)):
                # Pruning: đã sort nên nếu candidates[i] > remaining
                # thì các phần tử sau cũng lớn hơn → dừng luôn
                if candidates[i] > remaining:
                    break
 
                current.append(candidates[i])
                # Chú ý: start = i (không phải i+1) vì được chọn lại
                backtrack(i, current, remaining - candidates[i])
                current.pop()  # Backtrack
 
        backtrack(0, [], target)
        return result
 
# Chạy thử
sol = Solution()
print(sol.combinationSum([2, 3, 5], 7))
# [[2, 2, 3], [2, 5]]

5.6 Combination Sum II — Mỗi phần tử dùng tối đa 1 lần

Khác biệt chính:

1. start = i + 1 (không phải i) — không được chọn lại phần tử
2. Skip duplicate: if i > start and candidates[i] == candidates[i-1]: continue

def combination_sum2(candidates, target):
    result = []
    candidates.sort()
 
    def backtrack(start, current, remaining):
        if remaining == 0:
            result.append(current[:])
            return
 
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break
 
            # Skip duplicate ở cùng level
            if i > start and candidates[i] == candidates[i - 1]:
                continue
 
            current.append(candidates[i])
            backtrack(i + 1, current, remaining - candidates[i])  # i+1!
            current.pop()
 
    backtrack(0, [], target)
    return result
 
print(combination_sum2([10, 1, 2, 7, 6, 1, 5], 8))
# [[1,1,6], [1,2,5], [1,7], [2,6]]
from typing import List
 
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()  # QUAN TRỌNG: sort để skip duplicate
        result = []
 
        def backtrack(start: int, current: List[int], remaining: int):
            if remaining == 0:
                result.append(current[:])
                return
 
            for i in range(start, len(candidates)):
                if candidates[i] > remaining:
                    break  # Pruning
                # Skip duplicate ở cùng level đệ quy
                if i > start and candidates[i] == candidates[i - 1]:
                    continue
 
                current.append(candidates[i])
                backtrack(i + 1, current, remaining - candidates[i])  # i+1!
                current.pop()
 
        backtrack(0, [], target)
        return result
 
# Chạy thử
sol = Solution()
print(sol.combinationSum2([10, 1, 2, 7, 6, 1, 5], 8))
# [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]

5.7 Combination Sum III — Chọn k số từ 1-9

def combination_sum3(k, n):
    """Chọn k số từ 1-9, tổng = n"""
    result = []
 
    def backtrack(start, current, remaining):
        if len(current) == k:
            if remaining == 0:
                result.append(current[:])
            return  # Đã đủ k số, dù remaining != 0 cũng dừng
 
        for i in range(start, 10):  # 1 đến 9
            if i > remaining:
                break  # Pruning
 
            current.append(i)
            backtrack(i + 1, current, remaining - i)
            current.pop()
 
    backtrack(1, [], n)
    return result
 
print(combination_sum3(3, 7))
# [[1, 2, 4]]
 
print(combination_sum3(3, 9))
# [[1, 2, 6], [1, 3, 5], [2, 3, 4]]
from typing import List
 
class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        """Chọn k số từ 1-9, tổng = n."""
        result = []
 
        def backtrack(start: int, current: List[int], remaining: int):
            # Đã chọn đủ k số
            if len(current) == k:
                if remaining == 0:
                    result.append(current[:])
                return  # dù remaining != 0 cũng dừng
 
            for i in range(start, 10):  # số từ 1 đến 9
                if i > remaining:
                    break  # Pruning: số quá lớn → dừng
                current.append(i)
                backtrack(i + 1, current, remaining - i)
                current.pop()
 
        backtrack(1, [], n)
        return result
 
# Chạy thử
sol = Solution()
print(sol.combinationSum3(3, 7))   # [[1, 2, 4]]
print(sol.combinationSum3(3, 9))   # [[1, 2, 6], [1, 3, 5], [2, 3, 4]]

5.8 So sánh 3 biến thể

	Combination Sum I	Combination Sum II	Combination Sum III
Input	Mảng candidates	Mảng candidates (có thể trùng)	Số 1-9
Mỗi phần tử	Dùng không giới hạn	Dùng tối đa 1 lần	Dùng tối đa 1 lần
Start khi đệ quy	i (chọn lại)	i + 1 (không chọn lại)	i + 1
Xử lý duplicate	Không cần (phần tử distinct)	Sort + skip khi nums[i]==nums[i-1]	Không cần (1-9 distinct)
Điều kiện dừng	remaining == 0	remaining == 0	len k AND remaining 0

5.9 Phân tích Complexity

Combination Sum I

Time Complexity: O(N^(T/M))

Trong đó:

• N = số candidates
• T = target
• M = giá trị nhỏ nhất trong candidates

Chứng minh:

Chiều sâu tối đa của cây đệ quy = $T/M$ (chọn phần tử nhỏ nhất M liên tục cho đến khi bằng T).

Mỗi node có tối đa N nhánh con.

Tổng số node: ${\sum }_{k=0}^{T/M}{N}^k=O(N^{T/M})$.

Combination Sum II

Time Complexity: O(2^N)

Worst case mỗi phần tử chọn hoặc không, giống Subsets.

Combination Sum III

Time Complexity: O(C(9, k)) = $O\left(\genfrac{}{}{0ex}{}{9}{k}\right)$

Chọn k số từ 9 số. Worst case (k=4 hoặc k=5): $\left(\genfrac{}{}{0ex}{}{9}{4}\right)=126$.

5.10 Best Case / Worst Case

	Best Case	Worst Case
CS I	O(1) khi target < min(candidates)	O(N^(T/M))
CS II	O(1) khi target < min(candidates)	O(2^N)
CS III	O(1) khi n > 45 (1+…+9=45)	O(C(9,k)) = O(126)

5.11 Cải tiến

1. Sort + Pruning — khi candidates[i] > remaining, break ngay (vì đã sort, các phần tử sau cũng lớn hơn)
2. Early termination — kiểm tra remaining < 0 trước khi đệ quy
3. Frequency counting (cho CS II) — đếm tần suất mỗi phần tử, duyệt theo phần tử unique, mỗi phần tử chọn 0 đến freq[i] lần

# Cách tiếp cận frequency counting cho CS II
from collections import Counter
 
def combination_sum2_freq(candidates, target):
    result = []
    freq = sorted(Counter(candidates).items())  # [(val, count), ...]
 
    def backtrack(idx, current, remaining):
        if remaining == 0:
            result.append(current[:])
            return
        if idx == len(freq):
            return
 
        val, count = freq[idx]
 
        # Thử chọn val từ 0 đến min(count, remaining//val) lần
        for times in range(min(count, remaining // val) + 1):
            if times > 0:
                current.append(val)
            backtrack(idx + 1, current, remaining - val * times)
 
        # Backtrack: bỏ tất cả val đã thêm
        for _ in range(min(count, remaining // val)):
            if current and current[-1] == val:
                current.pop()
 
    backtrack(0, [], target)
    return result