Jumlah Subhimpunan Sama untuk Partisi

Diberikan larik bilangan bulat positif nums yang tidak kosong, tentukan apakah Anda dapat mempartisinya menjadi dua himpunan bagian dengan jumlah yang sama. Misalnya, [1, 5, 11, 5] dapat dipartisi menjadi [1, 5, 5] dan [11], yang keduanya berjumlah 11. Jika jumlah totalnya ganjil, jawabannya segera False. Jika tidak, kita perlu menemukan himpunan bagian yang jumlahnya total_sum // 2 — masalah jumlah himpunan bagian klasik.

Reduksi utamanya: jika jumlah total S genap dan suatu subhimpunan berjumlah S//2, elemen-elemen yang tersisa secara otomatis juga berjumlah S//2. Jadi, Partisi Jumlah Subhimpunan Sama direduksi menjadi: apakah ada subhimpunan nums yang berjumlah S//2? Ini adalah masalah klasik Jumlah Subhimpunan yang NP-lengkap, yang kita selesaikan dengan DP ransel 0/1 dalam waktu O(n × S).

Definisikan larik boolean dp[c], dengan dp[c] = True berarti ada subhimpunan yang jumlahnya tepat c. Inisialisasikan dp[0] = True (jumlah subhimpunan kosong adalah 0) dan semua elemen lainnya dengan False. Untuk setiap angka num, iterasikan kapasitas dari target turun hingga num (iterasi mundur ransel 0/1), lalu tetapkan dp[c] = dp[c] or dp[c - num].

Untuk [1, 5, 11, 5], total=22 dan target=11. Awalnya dp[0]=True. Setelah num=1: dp[1]=True. Setelah num=5: dp[5]=True, dp[6]=True. Setelah num=11: dp[11]=True (hanya menggunakan 11). Kita sudah menemukan dp[11]=True, tetapi tetap melanjutkan pemrosesan semua angka. Jawaban akhirnya: dp[11]=True, sehingga partisi dapat dilakukan.

Kita dapat menambahkan penghentian dini: jika dp[target] menjadi True kapan pun, segera kembalikan True. Hal ini dapat mempercepat skenario kasus terbaik secara drastis. Selain itu, jika satu elemen sama dengan target, kita dapat segera mengembalikan True. Jika satu elemen melebihi target, elemen tersebut tidak dapat menjadi bagian dari subhimpunan mana pun yang jumlahnya sama dengan target, tetapi kita tetap perlu memeriksa elemen lainnya.

Alternatifnya adalah mempertahankan himpunan jumlah yang dapat dicapai. Mulailah dengan {0}. Untuk setiap angka, tambahkan angka tersebut ke setiap jumlah dalam himpunan saat ini: reachable = reachable | {s + num for s in reachable}. Saring hasilnya agar hanya menyimpan jumlah yang tidak melebihi target. Pada akhirnya, periksa apakah target terdapat dalam himpunan. Pendekatan ini intuitif, tetapi dapat menggunakan lebih banyak memori dan mungkin lebih lambat dalam praktik.

Pendekatan DP berjalan dalam waktu O(n × S), dengan S = sum(nums), dan menggunakan ruang O(S) untuk larik boolean. Untuk batasan di LeetCode (n ≤ 200, jumlah ≤ 20.000), jumlahnya paling banyak 4.000.000 operasi—sangat cepat. Pendekatan himpunan memiliki kompleksitas asimtotik yang sama, tetapi mungkin lebih lambat dalam praktik karena biaya tambahan pembuatan himpunan.

Masalah terkait: menghitung jumlah subhimpunan yang jumlahnya sama dengan target. Ubah DP dari boolean menjadi bilangan bulat: dp[c] = number of ways to reach sum c. Gunakan penjumlahan sebagai pengganti OR: dp[c] += dp[c - num]. Inisialisasikan dp[0] = 1. Gunakan iterasi mundur yang sama. Generalisasi ini menunjukkan bagaimana templat ransel dapat disesuaikan untuk berbagai pertanyaan tentang subhimpunan.

Antisipasilah pertanyaan lanjutan berikut: (1) Bagaimana jika Anda perlu mengembalikan partisi yang sebenarnya? — diperlukan DP 2D untuk rekonstruksi. (2) Bagaimana jika elemen dapat bernilai negatif? — geser target, atau gunakan kamus, bukan larik. (3) Berapa kompleksitas waktunya? — O(n × sum). (4) Dapatkah Anda meningkatkan solusi jika banyak angka yang sama? — ya, gunakan penghitungan frekuensi untuk mengurangi jumlah iterasi luar. Selalu sampaikan pertukaran ini secara proaktif.

Partisi Jumlah Subhimpunan Sama adalah penerapan langsung ransel 0/1: itemnya adalah angka-angka, bobotnya sama dengan nilainya, dan kapasitas ransel sama dengan target. Kita menanyakan apakah nilai maksimum sama dengan target (kelayakan), bukan berapa nilai maksimumnya. Iterasi mundurnya sama; hanya operasinya yang berubah dari max menjadi boolean or. Mengenali kaitan ini dalam wawancara menunjukkan kemampuan pengenalan pola yang kuat.

Kasus tepi yang perlu ditangani: (1) larik dengan panjang 1 — satu elemen tidak dapat dibagi, sehingga selalu False; (2) semua elemen identik dengan jumlah elemen genap — mungkin berhasil atau tidak, bergantung pada nilai setiap elemen; (3) jumlah yang sangat besar — periksa batasan sebelum mengalokasikan larik DP; (4) elemen yang lebih besar daripada target — dapat dilewati karena tidak mungkin menjadi bagian dari subhimpunan yang jumlahnya sama dengan target. Pemeriksaan elemen maksimum sebagai penghentian dini menangani kasus (4) secara efisien.

Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.

Dalam pelajaran ini Anda mempelajari: Partisi Jumlah Subhimpunan Sama direduksi menjadi masalah jumlah subhimpunan dengan target = total//2, DP 1D boolean dp[c] menggunakan iterasi mundur yang identik dengan ransel 0/1, dan pendekatan ini dapat digeneralisasi untuk menghitung subhimpunan dengan mengganti OR boolean menggunakan penjumlahan bilangan bulat. Selanjutnya kita membahas Jumlah Sasaran, dengan mengubah penetapan tanda menjadi ransel berdasarkan perbedaan jumlah subhimpunan.