PricingLoginStart free
DSA Interview Prep · Pelajaran

Jumlah Subset Sama bagi Pembahagian

Rumuskan semula masalah pembahagian sebagai beg galas 0/1 dengan sasaran jumlah/2, lalu mengesan kebolehlaksanaan menggunakan tatasusunan DP boolean.

Pelajaran 3 daripada 413 langkah

Jumlah Subset Sama bagi Pembahagian ialah pelajaran DSA Interview Prep percuma di CoddyKit. Ini ialah pelajaran 3 daripada 4. Sebanyak 3 pelajaran dalam laluan pembelajaran ini boleh dibaca sepenuhnya secara percuma — selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan praktikal dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran DSA Interview Prep, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.

Pernyataan Masalah

Diberikan tatasusunan bukan kosong yang mengandungi integer positif nums, tentukan sama ada anda boleh membahagikannya kepada dua subhimpunan dengan jumlah yang sama. Sebagai contoh, [1, 5, 11, 5] boleh dibahagikan kepada [1, 5, 5] dan [11], yang kedua-duanya berjumlah 11. Jika jumlah keseluruhan adalah ganjil, jawapannya serta-merta ialah False. Jika tidak, kita perlu mencari subhimpunan yang jumlahnya total_sum // 2 — masalah jumlah subhimpunan yang klasik.

Pengurangan kepada Jumlah Subhimpunan

Pengurangan utama: jika jumlah keseluruhan S adalah genap dan satu subhimpunan berjumlah S//2, elemen yang tinggal secara automatik juga berjumlah S//2. Jadi, Pembahagian Jumlah Subhimpunan Sama Rata boleh dikurangkan kepada soalan: adakah mana-mana subhimpunan nombor berjumlah S//2? Ini ialah masalah Jumlah Subhimpunan NP-lengkap klasik, yang diselesaikan dengan DP masalah beg galas 0/1 dalam masa O(n × S).

def canPartition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False  # odd sum: impossible
    target = total // 2
    # Now: does any subset of nums sum to target?

Tatasusunan DP Boolean

Takrifkan tatasusunan boolean dp[c], dengan dp[c] = True bermaksud wujud subhimpunan yang jumlahnya tepat-tepat c. Mulakan dengan dp[0] = True (jumlah subhimpunan kosong ialah 0) dan tetapkan semua yang lain kepada False. Bagi setiap nombor num, lelar kapasiti daripada target turun hingga num (lelaran mengundur masalah beg galas 0/1), kemudian tetapkan dp[c] = dp[c] or dp[c - num].

def canPartition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    
    dp = [False] * (target + 1)
    dp[0] = True
    
    for num in nums:
        for c in range(target, num - 1, -1):  # backward: 0/1 knapsack
            dp[c] = dp[c] or dp[c - num]
    
    return dp[target]

print(canPartition([1, 5, 11, 5]))  # True
print(canPartition([1, 2, 3, 5]))   # False

Menelusuri Contoh

Bagi [1, 5, 11, 5], jumlah keseluruhan=22 dan sasaran=11. Pada mulanya, dp[0]=True. Selepas num=1: dp[1]=True. Selepas num=5: dp[5]=True, dp[6]=True. Selepas num=11: dp[11]=True (hanya menggunakan 11 itu sendiri). Kita sudah menemui dp[11]=True — tetapi kita terus memproses semua nombor. Jawapan akhir: dp[11]=True, jadi pembahagian adalah mungkin.

Pengoptimuman Penamatan Awal

Kita boleh menambah keluar awal: jika dp[target] menjadi True pada bila-bila masa, segera pulangkan True. Ini boleh mempercepatkan keadaan kes terbaik dengan ketara. Selain itu, jika mana-mana elemen tunggal sama dengan target, kita boleh segera memulangkan True. Jika mana-mana elemen tunggal melebihi target, elemen itu tidak boleh berada dalam mana-mana subhimpunan yang berjumlah sasaran, tetapi kita masih perlu memeriksa elemen yang lain.

def canPartition_fast(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    if max(nums) > target:  # any element > target makes it impossible
        return False
    
    dp = [False] * (target + 1)
    dp[0] = True
    
    for num in nums:
        for c in range(target, num - 1, -1):
            dp[c] = dp[c] or dp[c - num]
            if dp[target]:
                return True  # early exit
    
    return dp[target]

print(canPartition_fast([1, 5, 11, 5]))  # True

Menggunakan Himpunan Python Daripada Tatasusunan DP

Alternatifnya ialah mengekalkan himpunan jumlah yang boleh dicapai. Mulakan dengan {0}. Bagi setiap nombor, tambahkan nombor itu kepada setiap jumlah dalam himpunan semasa: reachable = reachable | {s + num for s in reachable}. Tapis supaya hanya jumlah yang tidak melebihi sasaran dikekalkan. Pada akhirnya, semak sama ada target terdapat dalam himpunan tersebut. Pendekatan ini mudah difahami tetapi boleh menggunakan lebih banyak memori dan mungkin lebih perlahan dalam amalan.

def canPartition_set(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    
    reachable = {0}
    for num in nums:
        reachable = {s + num for s in reachable if s + num <= target} | reachable
    
    return target in reachable

print(canPartition_set([1, 5, 11, 5]))  # True

Analisis Kerumitan

Pendekatan DP berjalan dalam masa O(n × S), dengan S = sum(nums), dan menggunakan ruang O(S) untuk tatasusunan boolean. Bagi kekangan dalam LeetCode (n ≤ 200, jumlah ≤ 20,000), ini menghasilkan paling banyak 4,000,000 operasi — sangat pantas. Pendekatan himpunan mempunyai kerumitan asimptotik yang sama tetapi mungkin lebih perlahan dalam amalan kerana overhed pembinaan himpunan.

Pengitlakan: Mengira Subhimpunan dengan Jumlah

Masalah yang berkaitan: kira bilangan subhimpunan yang berjumlah sasaran. Tukarkan DP daripada boolean kepada integer: dp[c] = number of ways to reach sum c. Gunakan penambahan dan bukannya OR: dp[c] += dp[c - num]. Mulakan dengan dp[0] = 1. Gunakan lelaran mengundur yang sama. Pengitlakan ini menunjukkan cara templat masalah beg galas boleh disesuaikan dengan soalan yang berbeza tentang subhimpunan.

def count_subsets(nums, target):
    dp = [0] * (target + 1)
    dp[0] = 1
    for num in nums:
        for c in range(target, num - 1, -1):
            dp[c] += dp[c - num]
    return dp[target]

print(count_subsets([1, 1, 1, 1, 1], 3))  # 10 (C(5,3))

Soalan Susulan Temu Duga Lazim

Jangkakan soalan susulan: (1) Bagaimana jika anda perlu memulangkan pembahagian sebenar? — ini memerlukan DP 2D untuk pembinaan semula. (2) Bagaimana jika elemen boleh bernilai negatif? — anjakkan sasaran, atau gunakan kamus dan bukannya tatasusunan. (3) Apakah kerumitan masa? — O(n × sum). (4) Bolehkah anda memperbaiknya jika banyak nombor adalah sama? — ya, gunakan pengiraan kekerapan untuk mengurangkan bilangan lelaran luaran. Sentiasa nyatakan pertukaran ini secara proaktif.

Menghubungkan dengan Masalah Beg Galas 0/1

Pembahagian Jumlah Subhimpunan Sama Rata ialah penggunaan langsung masalah beg galas 0/1: itemnya ialah nombor, beratnya sama dengan nilainya, dan kapasiti beg galas sama dengan sasaran. Kita bertanya sama ada nilai maksimum sama dengan sasaran (kebolehlaksanaan), bukannya apakah nilai maksimum itu. Lelaran mengundur adalah sama; hanya operasinya berubah daripada max kepada boolean or. Mengenali hubungan ini dalam temu duga menunjukkan keupayaan mengenal pasti corak yang kukuh.

Kes Tepi

Kes tepi yang perlu dikendalikan: (1) tatasusunan dengan panjang 1 — satu elemen tidak boleh dibahagikan, sentiasa False; (2) semua elemen sama dan bilangannya genap — mungkin berjaya atau tidak bergantung pada nilai setiap elemen; (3) jumlah yang sangat besar — semak kekangan sebelum memperuntukkan tatasusunan DP; (4) elemen yang lebih besar daripada sasaran — boleh dilangkau kerana tidak mungkin menjadi sebahagian daripada subhimpunan yang berjumlah sasaran. Semakan elemen maksimum sebagai keluar awal mengendalikan kes (4) dengan cekap.

Semakan Pantas

Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.

Jawab dalam pelajaran interaktif

Ulang Kaji Pelajaran

Dalam pelajaran ini, anda mempelajari bahawa: Pembahagian Jumlah Subhimpunan Sama Rata boleh dikurangkan kepada jumlah subhimpunan dengan sasaran = total//2, DP 1D boolean dp[c] menggunakan lelaran mengundur yang sama seperti masalah beg galas 0/1, dan pendekatan ini boleh digeneralisasikan untuk mengira subhimpunan dengan menggantikan OR boolean dengan penambahan integer. Seterusnya, kita akan mengendalikan Jumlah Sasaran dengan menukarkan penetapan tanda kepada masalah beg galas berdasarkan perbezaan jumlah subhimpunan.

Percuma untuk bermula

Pelajari Python dengan tutor kecerdasan buatan — percuma

Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.

Kursus
30
Pelajaran
120
Mula belajar secara percumaLihat kursus penuh

Soalan Lazim

Adakah pelajaran “Jumlah Subset Sama bagi Pembahagian” percuma?

Ya — sebanyak 3 pelajaran dalam laluan pembelajaran DSA Interview Prep, termasuk “Jumlah Subset Sama bagi Pembahagian”, boleh dibaca sepenuhnya secara percuma di web ini. Selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan interaktif dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.

Apakah yang akan saya pelajari dalam “Jumlah Subset Sama bagi Pembahagian”?

Rumuskan semula masalah pembahagian sebagai beg galas 0/1 dengan sasaran jumlah/2, lalu mengesan kebolehlaksanaan menggunakan tatasusunan DP boolean. Anda berlatih DSA Interview Prep menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.

Adakah saya memerlukan pengalaman untuk memulakan DSA Interview Prep?

Tiada pengalaman terdahulu diperlukan. Pembelajaran DSA Interview Prep di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 3 daripada 4.

Berapa lamakah pelajaran “Jumlah Subset Sama bagi Pembahagian” diambil?

Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.

Bolehkah saya menulis dan menjalankan kod dalam pelajaran DSA Interview Prep ini?

Ya. Setiap pelajaran DSA Interview Prep menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.

Semua pelajaran dalam kursus ini

  1. Beg Galas 0/1 dan Pengoptimuman Ruang
  2. Beg Galas Tanpa Had dan Pertukaran Syiling II
  3. Jumlah Subset Sama bagi Pembahagian
  4. Jumlah Sasaran dengan Tanda Positif dan Negatif
← Kembali ke DSA Interview Prep