Jumlah Subset & Partisi
Mencapai target dengan subset pilihan
Jumlah Subset & Partisi adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Pertanyaan Jumlah Himpunan Bagian
Diberikan sejumlah angka dan sebuah target, apakah ada himpunan bagian yang jumlahnya tepat sama dengan target tersebut? Ini adalah ransel ketika nilai sama dengan bobot.
DP Boolean, Bukan Nilai
Di sini Anda melacak keterjangkauan, bukan nilai maksimum. Misalkan dp[s] bernilai True jika ada himpunan bagian yang jumlahnya tepat sama dengan s.
dp = [False] * (target + 1)
dp[0] = TrueNol Selalu Dapat Dicapai
Himpunan bagian kosong memiliki jumlah nol, jadi dp[0] dimulai dengan True. Semua jumlah lainnya dimulai dengan False sampai ada angka yang membuktikan bahwa jumlah tersebut dapat dicapai.
Transisinya
Untuk setiap angka, tandai s sebagai dapat dicapai jika s - num sudah dapat dicapai. Satu angka dapat mengubah banyak jumlah menjadi True.
for num in nums:
for s in range(target, num - 1, -1):
dp[s] = dp[s] or dp[s - num]Mundur Lagi
Setiap angka digunakan paling banyak sekali, jadi perulangan bagian dalam berjalan mundur, sama seperti pada ransel 0/1. Arah maju akan menggunakan kembali sebuah angka.
Baca Hasilnya
Setelah semua angka diproses, dp[target] menjawab pertanyaannya. True berarti ada himpunan bagian yang valid; False berarti hal itu mustahil.
Masuk ke Partisi
Masalah partisi menanyakan: apakah Anda dapat membagi larik menjadi dua bagian dengan jumlah yang sama? Masalah ini langsung dapat direduksi menjadi jumlah himpunan bagian.
Bagi Dua Totalnya
Jika jumlah totalnya ganjil, dua bagian yang sama besar mustahil, jadi segera jawab tidak. Jika tidak, targetnya cukup total // 2.
total = sum(nums)
if total % 2:
return False
target = total // 2Gunakan Kembali Jumlah Himpunan Bagian
Sekarang cukup tanyakan apakah suatu himpunan bagian dapat mencapai total // 2. Jika satu bagian mencapai target, sisanya otomatis membentuk bagian kedua yang sesuai.
Kompleksitas
Biayanya berorde n kali target, yaitu batas semu-polynomial. Metode ini cepat ketika target kecil, tetapi lambat ketika jumlahnya sangat besar.
Satu Keluarga Masalah
Jumlah subhimpunan, partisi, dan ransel 0/1 memiliki satu mekanisme yang sama. Kenali pola ambil atau tinggalkan, lalu gunakan kembali perulangan yang sama.
Pemeriksaan Singkat
Uji reduksi partisi.
Ringkasan
Anda menyelesaikan jumlah subhimpunan dengan DP boolean dan perulangan mundur, lalu mengubah partisi menjadi pencapaian total // 2. Mekanisme yang sama, hasil baru. ✅
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Jumlah Subset & Partisi” gratis?
Ya — teks lengkap “Jumlah Subset & Partisi” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Jumlah Subset & Partisi”?
Mencapai target dengan subset pilihan Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.
Berapa lama pelajaran “Jumlah Subset & Partisi” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Knapsack 0/1: Ambil atau Tinggalkan
- Knapsack dengan Optimasi Ruang
- DP Tanpa Batas & Pertukaran Koin
- Jumlah Subset & Partisi