Bagaimanakah anda boleh mencari semua subset yang mungkin bagi set dengan n elemen menggunakan pendekatan rekursif?

Mencari Semua Subset Set

Dalam sains komputer, mencari semua subset bagi set tertentu adalah masalah klasik. Timbul persoalan seperti berikut:

Masalah:

Bagaimana untuk menentukan semua kemungkinan subset bagi set dengan n elemen?

Penyelesaian:

Pendekatan mudah untuk masalah ini terletak pada rekursi. Konsep ini berkisar pada idea bahawa:

• Untuk n=1, subset ialah {{}, {1}}
• Untuk n>1, kita boleh membahagikan subset bagi 1,...,n-1 kepada dua kumpulan: yang mengandungi n dan yang tidak mengandungi n. Menggabungkan kumpulan ini menghasilkan subset untuk 1,...,n.

Contoh:

Pertimbangkan n=5.

1. Cari subset bagi 1,...,4: {{}, {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}, {1, 2, 3, 4}}
2. Buat salinan dan tambah 5 kepada setiap subset: {{5}, {1, 5}, {2, 5}, {3, 5}, {4, 5}, {1, 2, 5}, {1, 3, 5}, { 1, 4, 5}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}, {1, 2, 3, 5}, {1, 2, 4, 5}, {1, 3, 4, 5}, {2, 3, 4, 5}, {1, 2, 3, 4, 5}}
3. Ambil penyatuan yang asal dan set diubah suai: {{}, {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}, {1, 2, 3, 4, 5}}

Pelaksanaan C:

#include <vector>

using namespace std;

vector<vector<int>> subsets(vector<int>& nums) {
    if (nums.empty()) return {{}};

    vector<vector<int>> prev = subsets(vector<int>(nums.begin(), nums.end() - 1));
    vector<vector<int>> curr;

    for (auto& subset : prev) {
        curr.push_back(subset);
        subset.push_back(nums.back());
        curr.push_back(subset);
    }

    return curr;
}

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