Enumerasi Subset dengan Bitmask
Mengiterasi semua subset melalui bilangan bulat
Enumerasi Subset dengan Bitmask adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 3 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.
Himpunan Bagian sebagai Bilangan
Setiap himpunan bagian dari n elemen dapat dipetakan ke satu bilangan bulat. Hitung dari 0 ke atas, dan bit pada setiap bilangan menentukan tepat elemen mana yang termasuk di dalamnya. 🙂
Berapa Banyak Himpunan Bagian
Sebuah himpunan yang berisi n elemen memiliki 2^n himpunan bagian. Jadi, melakukan iterasi pada bilangan bulat dari 0 hingga 2^n dikurangi 1 akan mengunjungi setiap himpunan bagian tepat satu kali.
for mask in range(1 << n):
pass # mask is one subset1 << n Menentukan Jumlah
Operasi geser 1 << n sama dengan 2 pangkat n. Ini adalah cara yang ringkas dan cepat untuk menuliskan batas atas iterasi himpunan bagian Anda.
Baca Bit i
Untuk mengetahui apakah elemen i berada dalam himpunan bagian, periksa bit-nya dengan masker dan 1 yang digeser ke kiri sebanyak i. Hasil yang bukan nol berarti elemen tersebut disertakan.
if mask & (1 << i):
take(items[i])Bangun Daftar Pilihan
Periksa setiap posisi bit dan kumpulkan elemen yang bit-nya bernilai 1. Dengan begitu, satu masker dapat diubah menjadi himpunan bagian konkret yang diwakilinya.
chosen = [items[i] for i in range(n) if mask & (1 << i)]Himpunan Kosong dan Penuh
Masker 0 adalah himpunan bagian kosong, sedangkan masker yang semua bit-nya bernilai 1 mewakili seluruh himpunan. Keduanya diperoleh secara otomatis karena iterasi Anda mencakup setiap nilai.
Jumlahkan Himpunan Bagian
Di dalam iterasi, jumlahkan elemen yang dipilih untuk menghitung nilai setiap himpunan bagian. Inilah inti dari banyak solusi pencarian menyeluruh sederhana.
total = sum(v[i] for i in range(n) if mask & (1 << i))Hitung Bit Bernilai 1
Jumlah elemen yang dipilih sama dengan banyaknya bit bernilai 1 pada masker. Dalam Python, bin(mask).count('1') langsung menghasilkan jumlah tersebut.
size = bin(mask).count("1")Perhatikan Batasnya
Karena ada 2^n himpunan bagian, teknik ini hanya cocok untuk n yang kecil. Sekitar n sama dengan 20 adalah batas praktis untuk enumerasi penuh.
Mengapa Masker Bit Unggul
Satu iterasi bilangan bulat menggantikan iterasi bertingkat yang rumit, dan operasi bit berlangsung cepat. Kodenya tetap singkat, jelas, dan mudah diuji.
Pola yang Dapat Digunakan Kembali
Lakukan iterasi pada masker, uraikan bit-bitnya, hitung nilai himpunan bagian, lalu catat hasil terbaik. Hafalkan templat ini agar banyak masalah himpunan bagian menjadi rutin.
Pemeriksaan Singkat
Anda ingin menguji apakah elemen i disertakan dalam himpunan bagian yang direpresentasikan oleh masker.
Ringkasan
Lakukan iterasi pada masker dari 0 hingga 2^n dikurangi 1, baca bit dengan masker dan 1 yang digeser ke kiri, lalu hitung nilai setiap himpunan bagian. Ini adalah pencarian menyeluruh yang ringkas untuk n kecil. 🚀
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Enumerasi Subset dengan Bitmask” gratis?
Ya — teks lengkap “Enumerasi Subset dengan Bitmask” 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 “Enumerasi Subset dengan Bitmask”?
Mengiterasi semua subset melalui bilangan bulat 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 3 dari 4.
Berapa lama pelajaran “Enumerasi Subset dengan Bitmask” 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
- Brute Force adalah Strategi yang Valid
- Enumerasi dengan itertools
- Enumerasi Subset dengan Bitmask
- Memangkas Ruang Pencarian dengan Cerdas