Combination Sum

Q: Tại sao bạn gọi đệ quy với i chứ không phải i + 1 trong bài Combination Sum?

Đệ quy với i cho phép giá trị tiếp theo vẫn là ứng viên đó, nhờ vậy một giá trị có thể được dùng nhiều lần. Đệ quy với i + 1 chuyển sang ứng viên kế tiếp, nên mỗi ứng viên chỉ có thể được dùng tối đa một lần.

Q: Có thể giải Combination Sum bằng quy hoạch động không?

Có. Với mỗi tổng từ 0 đến target , hãy giữ lại các tổ hợp tạo ra tổng đó, thêm từng ứng viên một để mỗi danh sách luôn tăng dần. Cách này không bao giờ khám phá một ngõ cụt hai lần, nhưng lưu mọi tổ hợp chưa hoàn chỉnh cho mọi tổng, nên tốn nhiều bộ nhớ hơn hẳn. Vì bản thân đầu ra có thể tăng theo cấp số nhân, quay lui thường là cách giải phù hợp.

Trung bìnhQuay lui

+10

Bạn có một danh sách candidates gồm các số nguyên dương khác nhau và một số nguyên dương target. Hãy tìm mọi tổ hợp các số trong danh sách có tổng đúng bằng target, mỗi số có thể được dùng bao nhiêu lần tùy ý. [2, 3, 3] và [3, 2, 3] là cùng một tổ hợp.

Trả về từng tổ hợp theo thứ tự tăng dần và các tổ hợp theo thứ tự từ điển: tại vị trí đầu tiên mà hai tổ hợp khác nhau, tổ hợp có giá trị nhỏ hơn sẽ đứng trước.

Hàm

combinationSum(candidates: integer-array, target: integer) → integer-2d-array

candidatesinteger-array: các giá trị khác nhau bạn có thể dùng, theo thứ tự bất kỳ và bao nhiêu lần tùy thích
targetinteger: Tổng của mọi tổ hợp phải đạt chính xác
Trả vềinteger-2d-array: mọi tổ hợp có tổng bằng mục tiêu, mỗi tổ hợp được sắp xếp theo thứ tự tăng dần và các tổ hợp được liệt kê theo thứ tự từ điển

Ràng buộc

1 ≤ candidates.length ≤ 50
2 ≤ candidates[i] ≤ 500
2 ≤ target ≤ 500
Tất cả giá trị trong candidates đều khác nhau, không theo thứ tự cụ thể nào.
Ít nhất một tổ hợp đạt đến target, và nhiều nhất 150 tổ hợp đạt đến.

Ví dụ

Đầu vào: candidates = [6, 2, 3]target = 8
Đầu ra: [[2, 2, 2, 2], [2, 3, 3], [2, 6]]
Giải thích: Bốn số 2, 2 + 3 + 3 và 2 + 6 đều bằng 8, được sắp xếp theo giá trị thứ hai. Không có số 2 thì chỉ còn các số 3 và 6, tổng của chúng là bội số của 3, mà 8 không phải là bội số của 3.

Đầu vào: candidates = [5, 3, 4]target = 11
Đầu ra: [[3, 3, 5], [3, 4, 4]]
Giải thích: 3 + 3 + 5 và 3 + 4 + 4 đều bằng 11, và [3, 3, 5] đứng trước vì giá trị thứ hai của nó là 3, nhỏ hơn 4. Không tổ hợp nào chỉ gồm các số 4 và 5 tạo thành 11.

Câu hỏi mở rộng

Mỗi ứng viên giờ chỉ có thể được dùng nhiều nhất một lần, và candidates có thể chứa các giá trị lặp lại. Bạn thay đổi cách tìm kiếm như thế nào để không có tổ hợp nào xuất hiện hai lần?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Bẫy nằm ở việc tạo cùng một tổ hợp hai lần: 2, 3, 3 và 3, 2, 3 đều là một đáp án. Hãy tạo từng tổ hợp theo thứ tự tăng dần để mỗi tổ hợp chỉ có đúng một cách tạo, đồng thời sắp xếp các giá trị ứng viên để một nhánh dừng lại ngay khi giá trị tiếp theo lớn hơn phần còn lại.

Hãy thử mọi số lần cho từng ứng viên

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Một tổ hợp được mô tả đầy đủ bằng số lần xuất hiện của mỗi giá trị ứng viên: [2, 3, 3] gồm một số 2, hai số 3 và không có số 6. Thử mọi số lượng cho mỗi giá trị ứng viên đã sắp xếp, từ target / c xuống 0, rồi giữ lại những lựa chọn có tổng đúng bằng target. Mỗi tổ hợp tương ứng với một danh sách số lượng, nên không tổ hợp nào bị tìm thấy hai lần. Thử số lượng lớn hơn trước sẽ tạo ra thứ tự từ điển: tại vị trí đầu tiên mà hai đáp án khác nhau, đáp án có nhiều bản sao hơn của một giá trị vẫn giữ giá trị đó, còn đáp án kia giữ một giá trị lớn hơn.

Với [2, 3, 6] và target 8, có 5 × 3 × 2 = 30 nút lá cho 3 đáp án. Mỗi giá trị ứng viên lớn hơn target / 2 sẽ làm số nút lá tăng gấp đôi, vì vậy 40 giá trị ứng viên như thế tạo ra 2^40, khoảng 10^12.

Thuật toán

Sắp xếp các số cần xét và lưu một số đếm cho mỗi giá trị.
Trong choose(i, total), thử từng số đếm k từ target / nums[i] giảm dần đến 0, rồi gọi choose(i + 1, total + k × nums[i]).
Khi đã có số đếm cho mọi giá trị, giữ lại tổ hợp nếu total bằng target và ghi tổ hợp đó ra từ các số đếm.
Gọi choose(0, 0).

def combinationSum(candidates, target):
    nums = sorted(candidates)
    counts = [0] * len(nums)
    result = []

    def choose(i, total):
        if i == len(nums):
            if total == target:
                combo = []
                for value, k in zip(nums, counts):
                    combo.extend([value] * k)
                result.append(combo)
            return
        # Most copies first, so the combinations come out in lexicographic order.
        for k in range(target // nums[i], -1, -1):
            counts[i] = k
            choose(i + 1, total + k * nums[i])
        counts[i] = 0

    choose(0, 0)
    return result

Quay lui theo thứ tự tăng dần và cắt tỉa

Ý tưởng

Sau khi bạn đặt nums[i], giá trị tiếp theo có thể lại là nums[i] hoặc bất kỳ giá trị nào đứng sau nó, không bao giờ là giá trị đứng trước. Mỗi tổ hợp chỉ có đúng một thứ tự tăng dần, nên chỉ có đúng một đường đi, và [3, 2, 3] không bao giờ được tạo ra.

Với [2, 3, 6] đã sắp xếp và mục tiêu là 8, các đường đi 2, 2, 2, 2 và 2, 3, 3 và 2, 6 đạt đến 8. Đường đi 2, 2, 3 còn lại 1 và dừng lại mà không xét đến 6, còn 3, 3 còn lại 2, không giá trị nào phù hợp. Cách này cần 12 lần gọi, so với 30 lá khi đếm.

Ở mỗi cấp, vòng lặp thử các giá trị nhỏ hơn trước, nên các đáp án xuất hiện theo thứ tự từ điển. Không đáp án nào là tiền tố của đáp án khác, vì các giá trị đều dương và cả hai đều đạt cùng một tổng.

Thuật toán

Sắp xếp các ứng viên.
Trong backtrack(start, remaining), lưu một bản sao của path dùng chung khi remaining bằng 0.
Nếu không, lặp i từ start. Nếu nums[i] > remaining, thoát vòng lặp: mọi giá trị phía sau đều lớn hơn.
Thêm nums[i], gọi backtrack(i, remaining - nums[i]), rồi xóa phần tử đó.
Gọi backtrack(0, target) và trả về các tổ hợp đã lưu.

def combinationSum(candidates, target):
    nums = sorted(candidates)
    result = []
    path = []

    def backtrack(start, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(nums)):
            if nums[i] > remaining:
                break  # sorted, so every later value is too big as well
            path.append(nums[i])
            backtrack(i, remaining - nums[i])  # i, not i + 1: nums[i] may repeat
            path.pop()

    backtrack(0, target)
    return result

Lỗi thường gặp và trường hợp biên

Lặp qua mọi ứng viên ở mỗi cấp thay vì bắt đầu từ chỉ số hiện tại. [2, 3, 3], [3, 2, 3] và [3, 3, 2] khi đó trở thành ba đáp án.
Gọi đệ quy với i + 1 thay vì i. Khi đó, mỗi giá trị chỉ có thể xuất hiện một lần, nên [2, 2, 2, 2] sẽ bị bỏ sót.
Lưu chính path thay vì lưu một bản sao. Khi đó, mọi đáp án được lưu đều là cùng một danh sách, mà thuật toán quay lui đã xóa hết khi kết thúc.
Dùng break với các ứng viên chưa được sắp xếp. Với [6, 2, 3] và số cần tìm còn lại là 2, vòng lặp dừng ở 6 và không bao giờ thử 2.

Câu hỏi thường gặp3

Độ phức tạp thời gian của Combination Sum là bao nhiêu?

Quá trình tìm kiếm bằng quay lui có độ phức tạp theo cấp số mũ. Với n ứng viên, mục tiêu t và ứng viên nhỏ nhất m, một tổ hợp có tối đa t/m giá trị với tối đa n lựa chọn cho mỗi giá trị: O(n^(t/m)). Không gian phụ là O(t/m) cho đường đi và ngăn xếp lời gọi, cộng thêm phần đầu ra.

Tại sao bạn gọi đệ quy với i chứ không phải i + 1 trong bài Combination Sum?

Đệ quy với i cho phép giá trị tiếp theo vẫn là ứng viên đó, nhờ vậy một giá trị có thể được dùng nhiều lần. Đệ quy với i + 1 chuyển sang ứng viên kế tiếp, nên mỗi ứng viên chỉ có thể được dùng tối đa một lần.

Có thể giải Combination Sum bằng quy hoạch động không?

Có. Với mỗi tổng từ 0 đến target, hãy giữ lại các tổ hợp tạo ra tổng đó, thêm từng ứng viên một để mỗi danh sách luôn tăng dần. Cách này không bao giờ khám phá một ngõ cụt hai lần, nhưng lưu mọi tổ hợp chưa hoàn chỉnh cho mọi tổng, nên tốn nhiều bộ nhớ hơn hẳn. Vì bản thân đầu ra có thể tăng theo cấp số nhân, quay lui thường là cách giải phù hợp.

def combinationSum(candidates, target):
    # Viết code tại đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

candidates = [6, 2, 3]
target = 8

Đầu ra mong đợi

[[2, 2, 2, 2], [2, 3, 3], [2, 6]]