Bagaimanakah anda mencari semua subset set menggunakan pendekatan rekursif?

Mencari Semua Subset Set

Memandangkan set n unsur, subset ialah sebarang gabungan unsur tersebut. Matlamatnya ialah untuk mencari algoritma komprehensif yang menjana semua subset yang mungkin.

Penyelesaian Rekursif

Pertimbangkan algoritma berikut:

• Kes Asas : Jika set mengandungi hanya satu elemen, algoritma mengembalikan set kosong dan set yang mengandungi elemen itu.
• Rekursif Langkah: Untuk set dengan n elemen, cari set subset bagi elemen n-1 yang pertama.
• Pembahagi: Bahagikan set sebelumnya kepada dua kumpulan: subset yang mengandungi unsur n dan subset yang tidak.
• Kesatuan: Ambil kesatuan kedua-dua kumpulan ini untuk membentuk set lengkap subset.

Contoh: {1,2,3,4,5}

Langkah 1: Cari semua subset {1,2,3, 4}. Ini ialah: {}, {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4} }, {3,4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4} dan {1,2,3,4} .

Langkah 2: Tambah 5 kepada setiap subset daripada Langkah 1 dan bersatu dengan subset:

• {} -> {}
• {1} -> {1} dan {1,5}
• {2} -> {2} dan {2,5}
• ...
• {1,2,3,4} -> {1,2,3,4} dan {1,2,3,4,5}

Kesatuan subset ini memberi kita set lengkap subset untuk {1,2,3, 4,5}:

{ {}, {1}, {2}, {3}, {4}, {5}, {1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}, {3,5}, {4,5}, {1 ,2,3}, {1,2,4}, {1,2,5}, {1,3,4}, {1,3,5}, {1,4,5}, {2,3 ,4}, {2,3,5}, {2,4,5}, {3,4,5}, {1,2,3,4}, {1,2,3,5}, {1,2,4,5}, {1,3 ,4,5}, {2,3,4,5} dan {1,2,3,4,5} }

Atas ialah kandungan terperinci Bagaimanakah anda mencari semua subset set menggunakan pendekatan rekursif?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!