Combination Sum

Q: Mengapa kamu melakukan rekursi dengan i, bukan i + 1, dalam Combination Sum?

Melakukan rekursi dengan i membuat nilai berikutnya menjadi kandidat yang sama lagi, sehingga nilai dapat digunakan lebih dari sekali. Melakukan rekursi dengan i + 1 melewatinya, sehingga setiap kandidat hanya dapat digunakan paling banyak sekali.

Q: Apakah Combination Sum dapat diselesaikan dengan pemrograman dinamis?

Ya. Untuk setiap total dari 0 hingga target , simpan kombinasi yang mencapainya, dengan menambahkan satu kandidat setiap kali agar setiap list tetap berurutan menaik. Cara ini tidak pernah menjelajahi jalan buntu dua kali, tetapi menyimpan setiap kombinasi parsial untuk setiap total, sehingga membutuhkan jauh lebih banyak memori. Karena output itu sendiri bisa berukuran eksponensial, backtracking biasanya menjadi solusi.

SedangBacktracking

+10

Kamu mendapatkan list candidates berisi bilangan bulat positif yang berbeda dan bilangan bulat positif target. Temukan semua kombinasi candidates yang jumlahnya tepat target, dengan menggunakan setiap kandidat sebanyak yang kamu inginkan. [2, 3, 3] dan [3, 2, 3] adalah kombinasi yang sama.

Kembalikan setiap kombinasi dalam urutan menaik, dan urutkan kombinasinya secara leksikografis: pada posisi pertama saat dua kombinasi berbeda, kombinasi dengan nilai yang lebih kecil berada lebih dahulu.

Fungsi

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

candidatesinteger-array: nilai yang berbeda yang boleh kamu gunakan, dalam urutan apa pun, sebanyak yang kamu mau
targetinteger: total setiap kombinasi harus mencapai tepat
Mengembalikaninteger-2d-array: setiap kombinasi yang jumlahnya sama dengan target, masing-masing dalam urutan menaik, dicantumkan dalam urutan leksikografis

Batasan

1 ≤ candidates.length ≤ 50
2 ≤ candidates[i] ≤ 500
2 ≤ target ≤ 500
Semua nilai dalam candidates berbeda, tanpa urutan tertentu.
Setidaknya satu kombinasi mencapai target, dan paling banyak 150 kombinasi mencapainya.

Contoh

Input: candidates = [6, 2, 3]target = 8
Output: [[2, 2, 2, 2], [2, 3, 3], [2, 6]]
Penjelasan: Empat angka 2, 2 + 3 + 3 dan 2 + 6 semuanya menghasilkan 8, diurutkan berdasarkan nilai keduanya. Tanpa angka 2, hanya tersisa angka 3 dan 6, dan jumlahnya merupakan kelipatan 3, sedangkan 8 bukan.

Input: candidates = [5, 3, 4]target = 11
Output: [[3, 3, 5], [3, 4, 4]]
Penjelasan: 3 + 3 + 5 dan 3 + 4 + 4 sama-sama menghasilkan 11, dan [3, 3, 5] berada di urutan pertama karena nilai keduanya, 3, lebih kecil daripada 4. Tidak ada kombinasi 4 dan 5 saja yang menghasilkan 11.

Pertanyaan lanjutan

Setiap kandidat kini dapat digunakan paling banyak satu kali, dan candidates dapat berisi nilai yang berulang. Bagaimana kamu mengubah pencarian agar tidak ada kombinasi yang muncul dua kali?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Jebakannya adalah membangun kombinasi yang sama dua kali: 2, 3, 3 dan 3, 2, 3 merupakan satu jawaban. Bangun setiap kombinasi dalam urutan menaik agar hanya ada satu jalur, lalu urutkan kandidat sehingga sebuah cabang berhenti segera setelah nilai berikutnya lebih besar daripada sisa yang tersedia.

Coba setiap jumlah untuk setiap kandidat

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Sebuah kombinasi dijelaskan sepenuhnya oleh jumlah salinan setiap kandidat yang digunakan: [2, 3, 3] berarti satu 2, dua 3, dan tidak ada 6. Coba setiap jumlah untuk tiap kandidat yang sudah diurutkan, dari target / c hingga 0, lalu pertahankan pilihan yang jumlahnya tepat target. Setiap kombinasi memiliki satu daftar jumlah, jadi tidak ada kombinasi yang ditemukan dua kali. Jumlah yang lebih besar lebih dahulu menghasilkan urutan leksikografis: saat dua jawaban pertama kali berbeda, jawaban yang memiliki lebih banyak salinan suatu nilai tetap memuat nilai itu, sedangkan jawaban lainnya memuat nilai yang lebih besar.

Untuk [2, 3, 6] dan target 8, ada 5 × 3 × 2 = 30 daun untuk 3 jawaban. Setiap kandidat yang lebih besar dari target / 2 menggandakan jumlah daun, jadi 40 kandidat seperti itu berarti 2^40, sekitar 10^12.

Algoritma

Urutkan kandidat dan simpan satu jumlah untuk setiap nilai.
Di choose(i, total), coba setiap jumlah k dari target / nums[i] turun hingga 0, lalu panggil choose(i + 1, total + k × nums[i]).
Setelah setiap nilai memiliki jumlah, simpan kombinasi jika total sama dengan target, lalu tuliskan kombinasi tersebut berdasarkan jumlahnya.
Panggil 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

Telusuri kembali dalam urutan menaik dan pangkas

Intuisi

Setelah kamu menempatkan nums[i], nilai berikutnya bisa berupa nums[i] lagi atau nilai mana pun setelahnya, tidak pernah nilai sebelumnya. Kombinasi memiliki tepat satu urutan menaik, jadi hanya ada satu jalur, dan [3, 2, 3] tidak pernah dibentuk.

Untuk [2, 3, 6] yang sudah diurutkan dan target 8, jalur 2, 2, 2, 2 serta 2, 3, 3 dan 2, 6 mencapai 8. Jalur 2, 2, 3 menyisakan 1 dan berhenti tanpa memeriksa 6, sedangkan 3, 3 menyisakan 2, yang tidak cocok dengan nilai mana pun. Jumlahnya 12 pemanggilan dibandingkan dengan 30 daun dalam pencacahan.

Di setiap level, perulangan mencoba nilai yang lebih kecil terlebih dahulu, jadi jawaban muncul dalam urutan leksikografis. Tidak ada jawaban yang menjadi awalan bagi jawaban lainnya, karena nilainya positif dan keduanya mencapai total yang sama.

Algoritma

Urutkan kandidat.
Di backtrack(start, remaining), simpan salinan path bersama saat remaining bernilai 0.
Jika tidak, lakukan perulangan i dari start. Jika nums[i] > remaining, break: setiap nilai setelahnya lebih besar.
Tambahkan nums[i], panggil backtrack(i, remaining - nums[i]), lalu hapus nilai tersebut.
Panggil backtrack(0, target) dan kembalikan kombinasi yang tersimpan.

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

Jebakan dan kasus tepi

Melakukan perulangan pada setiap kandidat di setiap tingkat, bukan mulai dari indeks saat ini. [2, 3, 3], [3, 2, 3], dan [3, 3, 2] kemudian muncul sebagai tiga jawaban.
Melakukan rekursi dengan i + 1, bukan i. Setiap nilai kemudian hanya dapat muncul sekali, sehingga [2, 2, 2, 2] tidak ditemukan.
Menyimpan path itu sendiri, bukan salinannya. Setiap jawaban yang disimpan kemudian menjadi list yang sama, yang telah dikosongkan oleh backtracking pada akhirnya.
Menggunakan break pada kandidat yang tidak kamu urutkan. Dengan [6, 2, 3] dan sisa 2, perulangan berhenti pada 6 dan tidak pernah mencoba 2.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Combination Sum?

Pencarian dengan backtracking bersifat eksponensial. Dengan n kandidat, target t, dan kandidat terkecil m, sebuah kombinasi memuat paling banyak t/m nilai dengan paling banyak n pilihan untuk setiap nilai: O(n^(t/m)). Ruang ekstra yang digunakan adalah O(t/m) untuk jalur dan call stack, ditambah output.

Mengapa kamu melakukan rekursi dengan i, bukan i + 1, dalam Combination Sum?

Melakukan rekursi dengan i membuat nilai berikutnya menjadi kandidat yang sama lagi, sehingga nilai dapat digunakan lebih dari sekali. Melakukan rekursi dengan i + 1 melewatinya, sehingga setiap kandidat hanya dapat digunakan paling banyak sekali.

Apakah Combination Sum dapat diselesaikan dengan pemrograman dinamis?

Ya. Untuk setiap total dari 0 hingga target, simpan kombinasi yang mencapainya, dengan menambahkan satu kandidat setiap kali agar setiap list tetap berurutan menaik. Cara ini tidak pernah menjelajahi jalan buntu dua kali, tetapi menyimpan setiap kombinasi parsial untuk setiap total, sehingga membutuhkan jauh lebih banyak memori. Karena output itu sendiri bisa berukuran eksponensial, backtracking biasanya menjadi solusi.

def combinationSum(candidates, target):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

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

Output yang diharapkan

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