Jumlah Target dengan Tanda Positif dan Negatif
Ubah masalah penetapan target-sum menjadi knapsack berdasarkan perbedaan subset-sum, lalu selesaikan dalam waktu O(n × sum)
Jumlah Target dengan Tanda Positif dan Negatif adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 4 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.
Masalah Jumlah Sasaran
Diberikan larik bilangan bulat nums dan bilangan bulat target, berikan tanda + atau - pada setiap angka sehingga ekspresi yang dihasilkan bernilai target. Kembalikan jumlah cara berbeda untuk melakukannya. Misalnya, untuk nums=[1,1,1,1,1] dan target=3, ada 5 cara (memilih 4 elemen agar positif dan 1 elemen agar negatif pada posisi yang berbeda).
Pencarian Menyeluruh: Enumerasi DFS
Pendekatan DFS memberikan tanda + atau - pada setiap angka dan melakukan pemanggilan rekursif, lalu mengembalikan jumlah simpul daun yang mencapai target. Pendekatan ini benar, tetapi memiliki kompleksitas waktu O(2^n)—eksponensial. Untuk n=20, terdapat lebih dari satu juta pemanggilan rekursif. Pendekatan DFS layak disebutkan terlebih dahulu, lalu segera beralih ke optimasi DP.
def findTargetSumWays_dfs(nums, target):
count = [0]
def dfs(i, current_sum):
if i == len(nums):
if current_sum == target:
count[0] += 1
return
dfs(i+1, current_sum + nums[i])
dfs(i+1, current_sum - nums[i])
dfs(0, 0)
return count[0]
print(findTargetSumWays_dfs([1,1,1,1,1], 3)) # 5DFS dengan Memoisasi
Tambahkan memoization ke DFS: keadaannya adalah (index, current_sum). Karena current_sum dapat berkisar dari -total hingga +total, terdapat O(n × total) keadaan unik. Dengan memoization, DFS berjalan dalam waktu dan ruang O(n × total). Pendekatan ini dapat digunakan dan valid dalam wawancara, tetapi DP berbasis transformasi lebih elegan dan lebih hemat ruang.
from functools import lru_cache
def findTargetSumWays_memo(nums, target):
total = sum(nums)
@lru_cache(maxsize=None)
def dp(i, remaining):
if i == len(nums):
return 1 if remaining == 0 else 0
return dp(i+1, remaining - nums[i]) + dp(i+1, remaining + nums[i])
return dp(0, target)
print(findTargetSumWays_memo([1,1,1,1,1], 3)) # 5Transformasi Matematis
Misalkan P adalah himpunan angka yang diberi tanda + dan N adalah himpunan angka yang diberi tanda -. Maka: sum(P) - sum(N) = target dan sum(P) + sum(N) = total. Dengan menjumlahkannya: 2 × sum(P) = target + total, sehingga sum(P) = (target + total) / 2. Masalah ini direduksi menjadi: menghitung subhimpunan nums yang jumlahnya (target + total) / 2. Ini tepat merupakan varian “menghitung subhimpunan” dari ransel 0/1.
# sum(P) - sum(N) = target
# sum(P) + sum(N) = total
# => 2*sum(P) = target + total
# => sum(P) = (target + total) / 2
# Count subsets with sum = new_target = (target + total) // 2
print('Reduction: count subsets summing to (target + total) // 2')Pemeriksaan Keabsahan Sebelum DP
Sebelum menjalankan DP, periksa hal-hal berikut: (1) target + total harus genap (jika tidak, sum(P) bukan bilangan bulat—mustahil); (2) abs(target) > total berarti target tidak dapat dicapai, bahkan jika semua tanda searah. Jika salah satu pemeriksaan gagal, segera kembalikan 0. Pemeriksaan ini menangani kasus tepi dengan rapi tanpa memerlukan penanganan khusus di dalam perulangan DP.
def findTargetSumWays(nums, target):
total = sum(nums)
if (target + total) % 2 != 0:
return 0 # sum(P) would be non-integer
if abs(target) > total:
return 0 # impossible to reach
new_target = (target + total) // 2
# Count subsets summing to new_target
dp = [0] * (new_target + 1)
dp[0] = 1
for num in nums:
for c in range(new_target, num - 1, -1):
dp[c] += dp[c - num]
return dp[new_target]
print(findTargetSumWays([1,1,1,1,1], 3)) # 5Menelusuri Contoh Kecil
Untuk nums=[1,1,1,1,1] dan target=3: total=5, new_target=(3+5)//2=4. Kita menghitung subhimpunan yang jumlahnya 4 dari [1,1,1,1,1]. Ini adalah C(5,4)=5 (memilih 4 angka satu untuk diberi tanda positif, sedangkan angka kelima diberi tanda negatif: 1+1+1+1-1=3). DP mengembalikan 5 dengan benar. Transformasi ini secara elegan memetakan masalah penetapan tanda menjadi masalah standar penghitungan subhimpunan.
Menangani Nol dalam nums
Jika nums berisi angka nol, memberikan tanda + atau - pada angka nol tidak mengubah jumlah. Setiap angka nol menggandakan jumlah penetapan yang valid. DP menanganinya secara alami: saat memproses num=0, perulangan bagian dalam range(new_target, -1, -1) berjalan dari new_target turun hingga 0, dan dp[c] += dp[c - 0] = dp[c] menggandakan semua jumlah yang dapat dicapai. Tidak diperlukan penanganan khusus jika Anda menggunakan range(new_target, num-1, -1), yang saat num=0 dimulai dari new_target dan berjalan turun hingga 0.
# With zeros: each zero doubles the count
print(findTargetSumWays([0, 0, 1], 1)) # 4
# Assignments: +0+0+1, +0-0+1, -0+0+1, -0-0+1 = all give sum 1Perbandingan Kompleksitas
DFS pencarian menyeluruh adalah O(2^n). DFS dengan memoization memiliki waktu O(n × total) dan ruang O(n × total). DP 1D berbasis transformasi memiliki waktu O(n × new_target) dan ruang O(new_target), dengan new_target ≤ total. DP 1D menggunakan ruang yang jauh lebih sedikit daripada memoization karena menghapus dimensi indeks melalui transformasi.
Kaitan dengan Masalah Ransel Lain
Jumlah Sasaran menghubungkan beberapa konsep ransel: masalah ini dimulai sebagai masalah penetapan, ditransformasikan menjadi jumlah subhimpunan (seperti Partisi Jumlah Subhimpunan Sama), dan menggunakan templat iterasi mundur ransel 0/1 yang sama, tetapi dengan penghitungan (seperti Penukaran Koin II). Menguasai kaitan ini memungkinkan Anda mengelompokkan masalah baru dengan cepat dalam wawancara berdasarkan kemiripan strukturnya dengan pola yang sudah dikenal.
Kasus Tepi dan Catatan Wawancara
Kasus-kasus penting: (1) target = total: hanya ada satu cara (semuanya positif); (2) target = -total: hanya ada satu cara (semuanya negatif); (3) target = 0 dengan semua angka nol: jawabannya adalah 2^n; (4) total yang sangat besar tetapi n kecil — ukuran larik DP 1D dibatasi oleh total/2. Dalam wawancara, jelaskan langkah transformasi secara lisan sebelum menulis kode—inilah wawasan yang tidak langsung terlihat dan membedakan kandidat yang kuat.
Alternatif DP 2D Tanpa Transformasi
Tanpa transformasi, definisikan dp[i][s] sebagai jumlah cara memberikan tanda pada i angka pertama hingga mencapai jumlah s. Jumlah tersebut dapat bernilai negatif, jadi gunakan pergeseran sebesar total: dp[i][s + total]. Cara ini memerlukan tabel 2D berukuran (n+1) × (2*total+1). Meskipun benar, cara ini menggunakan lebih banyak ruang dan lebih sulit ditulis dengan cepat di bawah tekanan wawancara dibandingkan ransel 1D setelah transformasi.
Pemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini Anda mempelajari: Jumlah Sasaran mengubah penetapan tanda menjadi penghitungan subhimpunan yang jumlahnya (target + total) / 2, ransel 0/1 1D dengan iterasi mundur menghitung subhimpunan dalam waktu O(n × new_target) dan ruang O(new_target), dan pemeriksaan keabsahan awal (jumlah ganjil, |target| > total) mencegah eksekusi DP yang tidak diperlukan. Selanjutnya kita memasuki ranah jalur terpendek dengan algoritma Dijkstra dan antrean prioritas.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Jumlah Target dengan Tanda Positif dan Negatif” gratis?
Ya — teks lengkap “Jumlah Target dengan Tanda Positif dan Negatif” 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 “Jumlah Target dengan Tanda Positif dan Negatif”?
Ubah masalah penetapan target-sum menjadi knapsack berdasarkan perbedaan subset-sum, lalu selesaikan dalam waktu O(n × sum) 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 4 dari 4.
Berapa lama pelajaran “Jumlah Target dengan Tanda Positif dan Negatif” 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
- Knapsack 0/1 dan Optimasi Ruang
- Knapsack Tak Terbatas dan Coin Change II
- Jumlah Subhimpunan Sama untuk Partisi
- Jumlah Target dengan Tanda Positif dan Negatif