Subsets

+10

Kamu mendapatkan sebuah list nums berisi bilangan bulat yang berbeda. Kembalikan setiap subset dari list tersebut, termasuk subset kosong dan list lengkapnya, sehingga n nilai menghasilkan 2^n subset. Tulis setiap subset dengan nilai-nilainya dalam urutan menaik, dan urutkan subset secara leksikografis: bandingkan dua subset nilai demi nilai, perbedaan pertama menentukan urutannya, dan subset yang merupakan awal dari subset lain muncul lebih dulu. Untuk [1, 2], jawabannya adalah [[], [1], [1, 2], [2]].

Fungsi

subsets(nums: integer-array) → integer-2d-array

numsinteger-array: nilai-nilainya, semuanya berbeda, dalam urutan apa pun
Mengembalikaninteger-2d-array: setiap subset, masing-masing diurutkan menaik, dicantumkan dalam urutan leksikografis

Batasan

1 ≤ nums.length ≤ 10
-10 ≤ nums[i] ≤ 10
Semua nilai dalam nums berbeda.
nums dapat muncul dalam urutan apa pun.

Contoh

Input: nums = [3, 1, 2]
Output: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
Penjelasan: Tiga nilai menghasilkan 2^3 = 8 subset. [1, 2] muncul sebelum [1, 2, 3] karena merupakan awalnya, dan [1, 2, 3] muncul sebelum [1, 3] karena 2 lebih kecil daripada 3 pada posisi kedua.

Input: nums = [0]
Output: [[], [0]]
Penjelasan: Satu nilai memiliki dua subset: abaikan nilai tersebut dan dapatkan [], atau ambil nilai tersebut dan dapatkan [0]. Subset kosong selalu muncul lebih dahulu.

Input: nums = [5, -2]
Output: [[], [-2], [-2, 5], [5]]
Penjelasan: Nilainya diurutkan menjadi -2 dan 5, jadi [-2, 5] ditulis dalam urutan tersebut. Setiap subset yang memuat -2 berada sebelum [5], karena -2 lebih kecil daripada 5.

Pertanyaan lanjutan

Bisakah kamu menghasilkan list yang sama tanpa rekursi, dengan membangun setiap subset langsung dari subset sebelumnya?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Ada 2^n subset, jadi tidak ada cara yang membutuhkan kurang dari O(2^n) pekerjaan. Pertanyaan sebenarnya adalah bagaimana menghasilkan setiap subset tepat satu kali, dalam urutan yang diperlukan, tanpa mengurutkan 1024 daftar setelahnya. Dengan melakukan backtracking pada nilai yang sudah diurutkan dan mencatat setiap simpul pohon keputusan saat kamu memasukinya, subset akan ditelusuri tepat dalam urutan leksikografis.

Bitmask, lalu urutkan

Intuisi

Susun nilai yang sudah diurutkan pada posisi 0 hingga n-1. n bit dari sebuah bilangan menentukan ya atau tidak untuk setiap posisi, jadi bilangan dari 0 hingga 2^n-1 adalah subset, masing-masing tepat satu kali: untuk [1, 2, 3], mask 5 adalah biner 101 dan mewakili [1, 3]. Membaca bit mulai dari posisi 0 akan menuliskan setiap subset dalam urutan menaik.

Mask muncul dalam urutan yang salah: mask 2 adalah [2] dan mask 3 adalah [1, 2], jadi [2] muncul sebelum [1, 2]. Pengurutan yang membandingkan nilai satu per satu dan menempatkan prefiks lebih dulu dapat memperbaikinya. Pengurutan itu membutuhkan sekitar n × 2^n perbandingan, masing-masing hingga n nilai, sekitar 10^5 pembacaan saat n = 10, pekerjaan yang tidak pernah dilakukan oleh backtracking.

Algoritma

Urutkan nums agar setiap subset tersusun dalam urutan menaik.
Untuk setiap mask dari 0 hingga 2^n-1, kumpulkan nilai pada posisi yang bitnya aktif.
Urutkan list subset: pada posisi pertama saat dua subset berbeda, nilai yang lebih kecil berada lebih dulu, dan jika salah satunya habis lebih dulu, subset itu berada lebih dulu.
Kembalikan list yang sudah diurutkan.

def subsets(nums):
    values = sorted(nums)
    n = len(values)
    result = []
    for mask in range(1 << n):
        # Bit i of mask says whether values[i] is in this subset.
        result.append([values[i] for i in range(n) if (mask >> i) & 1])
    # Python compares lists position by position, and a prefix comes first.
    result.sort()
    return result

Backtracking: pilih, jelajahi, batalkan pilihan

Intuisi

Bayangkan subset sebagai pohon. Akarnya adalah subset kosong, dan di bawah sebuah simpul, kamu bisa menambahkan nilai apa pun yang lebih besar dari nilai terakhirnya: untuk [1, 2, 3], [1] memiliki anak [1, 2] dan [1, 3]. Setiap subset muncul satu kali, karena hanya ada satu cara menuliskannya secara menaik, dan setiap simpul adalah jawaban, termasuk simpul di bagian dalam.

Backtracking menelusuri pohon dengan satu list bersama, path, dan mencatat salinannya saat tiba di setiap simpul. Dengan begitu, setiap simpul induk muncul sebelum anak-anaknya, dan mencoba anak dari nilai terkecil ke terbesar akan menyelesaikan satu cabang sebelum cabang berikutnya: urutan leksikografis tanpa pengurutan.

Pohon ini memiliki 2^n simpul dan setiap penyalinan membutuhkan hingga n: O(n × 2^n), sebesar ukuran jawaban, ditambah O(n) untuk path dan tumpukan pemanggilan.

Algoritma

Urutkan nilai-nilainya.
Tulis explore(start). Fungsi ini terlebih dahulu menambahkan salinan path ke hasil.
Lalu, untuk setiap indeks i dari start hingga akhir: tambahkan values[i] ke path (pilih), panggil explore(i+1) (jelajahi), lalu hapus nilai terakhir (batalkan pilihan).
Panggil explore(0) dengan path kosong, lalu kembalikan hasilnya.

def subsets(nums):
    values = sorted(nums)
    result = []
    path = []

    def explore(start):
        # Every node of the decision tree is a subset: record it on the way in.
        result.append(path[:])
        for i in range(start, len(values)):
            path.append(values[i])  # choose
            explore(i + 1)          # explore: only larger values may follow
            path.pop()              # un-choose

    explore(0)
    return result

Jebakan dan kasus tepi

Menambahkan path itu sendiri, bukan salinannya. Setiap entri kemudian menunjuk ke satu list, yang kosong saat penelusuran berakhir, sehingga kamu mengembalikan 2^n salinan [].
Lupa mengurutkan nums. Dengan [3, 1, 2], pohon membentuk [3, 1], yang tidak berurutan menaik.
Mencatat hanya di daun, seperti pada permutasi. Setiap simpul adalah subset, jadi kamu mengembalikan terlalu sedikit.
Melakukan rekursi pada start+1, bukan i+1. Nilai kemudian dapat mengikuti nilai yang lebih besar atau dirinya sendiri, sehingga menghasilkan list seperti [3, 2] dan [1, 3, 3].
Mencatat daun dari pohon yang menyertakan atau mengecualikan elemen. Cara ini menemukan semua 2^n subset, tetapi menyertakan elemen terlebih dahulu menempatkan list lengkap di urutan pertama, sedangkan mengecualikan elemen terlebih dahulu menempatkan [3] sebelum [2].

Pertanyaan yang sering diajukan3

Berapa banyak subset yang dimiliki sebuah set dengan n elemen?

2^n. Setiap elemen dipilih atau tidak dipilih, terlepas dari elemen lainnya, sehingga jumlah pilihannya dikalikan. Tiga nilai menghasilkan 8 himpunan bagian dan sepuluh menghasilkan 1024, termasuk himpunan bagian kosong dan set penuh.

Berapa kompleksitas waktu dari masalah Subsets?

O(n × 2^n). Ada 2^n subset dan menuliskan satu subset membutuhkan hingga n langkah, jadi hanya mengembalikan jawabannya saja membutuhkan biaya sebesar itu. Backtracking mencapai batas ini dengan ruang tambahan O(n); bitmask yang diikuti pengurutan menambahkan faktor n lagi.

Bagaimana cara menangani nilai duplikat dalam Subsets?

Urutkan nilainya, lalu di dalam perulangan helper, lewati nilai yang sama dengan nilai sebelumnya pada level yang sama: i > start dan values[i] == values[i-1]. Salinan pertama sudah menjelajahi semua subset yang menggunakannya, jadi cabang yang dimulai dengan salinan kedua akan membentuk ulang subset yang sama.

def subsets(nums):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

nums = [3, 1, 2]

Output yang diharapkan

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]