Target Sum

Q: Bagaimana Target Sum berkaitan dengan masalah subset sum?

Angka-angka dengan tanda plus harus berjumlah (S + target) / 2 , jadi jawabannya adalah jumlah subset dari nums dengan jumlah tersebut. DP untuk menghitung subset dengan jumlah tertentu dapat menyelesaikannya setelah kamu menambahkan dua pemeriksaan: nilainya harus berupa bilangan bulat, dan |target| tidak boleh lebih besar dari S .

Q: Apa kompleksitas waktu dari Target Sum?

DP penghitungan subset berjalan dalam waktu O(n × S) dengan memori O(S) , dengan S sebagai jumlah nums . Rekursi dengan memoization memiliki waktu yang sama, tetapi menggunakan tabel n × (2S+1) . Mencoba setiap tanda membutuhkan O(2^n) .

SedangDynamic programming Backtracking

+10

Kamu mendapatkan sebuah array nums berisi bilangan bulat nonnegatif dan sebuah bilangan bulat target. Letakkan tanda plus atau minus di depan setiap angka, pertahankan urutannya, lalu hitung nilai ekspresinya. Kembalikan jumlah pilihan tanda yang membuat ekspresi bernilai target. Setiap satu dari 2^n pilihan dihitung secara terpisah, jadi +0 dan -0 adalah dua pilihan yang berbeda.

Fungsi

findTargetSumWays(nums: integer-array, target: integer) → integer

numsinteger-array: angka-angka, yang masing-masing mendapat tanda
targetinteger: nilai yang harus sama dengan ekspresi
Mengembalikaninteger: jumlah pilihan tanda yang ekspresinya sama dengan target

Batasan

1 ≤ nums.length ≤ 20
0 ≤ nums[i] ≤ 1000
Jumlah nums paling banyak 1000.
-1000 ≤ target ≤ 1000
Jawabannya paling banyak 2²⁰, jauh di bawah batas bilangan bulat bertanda 32-bit.

Contoh

Input: nums = [2, 1, 1]target = 2
Output: 2
Penjelasan: +2 +1 -1 dan +2 -1 +1 keduanya sama dengan 2. Dengan tanda minus pada 2, nilai terbesar yang bisa kamu capai adalah -2 + 1 + 1 = 0, jadi tidak ada pilihan lain yang berhasil.

Input: nums = [0, 4, 4]target = 0
Output: 4
Penjelasan: Kedua angka 4 harus memiliki tanda yang berlawanan, +4 -4 atau -4 +4, dan dalam kedua kasus, 0 bisa menggunakan tanda apa pun. Jadi, ada 2 × 2 = 4 pilihan.

Pertanyaan lanjutan

Bisakah kamu menangani hingga 40 angka dengan nilai hingga 10^9, saat tidak ada array yang diindeks berdasarkan jumlah yang muat di memori?

Petunjuk

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

0 dari 3 dibuka

Solusi

Setiap angka memiliki dua tanda, jadi ada 2^n ekspresi. Penghitungan berdasarkan posisi dan jumlah berjalan menggabungkan prefiks tanda yang mencapai jumlah yang sama. Lebih baik lagi, angka bertanda plus membentuk subset dengan jumlah tetap, sehingga masalah ini menjadi menghitung subset dengan jumlah tertentu, dalam waktu O(n × S) dengan S sebagai jumlah dari nums.

Coba kedua tanda untuk setiap angka

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Telusuri angka dari kiri ke kanan dengan total sementara, lalu buat dua percabangan pada setiap angka: tambahkan atau kurangi. Setelah setiap angka memiliki tanda, hitung 1 jika totalnya sama dengan target. Setiap pilihan tanda merupakan tepat satu jalur, jadi jumlahnya menghasilkan jawaban.

Setiap pilihan menghasilkan satu simpul daun: 2^20 ≈ 10^6 simpul daun untuk 20 angka, dan setiap angka tambahan menggandakan pekerjaan.

Algoritma

Tulis count(i, total), jumlah cara untuk memberi tanda pada nums[i..] ketika angka sebelum i sudah berjumlah total.
Jika i == n, kembalikan 1 saat total == target, jika tidak, kembalikan 0.
Jika tidak, kembalikan count(i+1, total + nums[i]) + count(i+1, total - nums[i]).
Jawabannya adalah count(0, 0).

def findTargetSumWays(nums, target):
    n = len(nums)

    def count(i, total):
        # Ways to sign nums[i:] so that the whole expression ends at target
        if i == n:
            return 1 if total == target else 0
        return count(i + 1, total + nums[i]) + count(i + 1, total - nums[i])

    return count(0, 0)

Memoisasikan berdasarkan posisi dan total berjalan

Intuisi

count(i, total) hanya bergantung pada i dan total, bukan pada tanda yang menghasilkan jumlah tersebut. Dengan nums = [1, 1, 1, 1], awalan +1 -1 dan -1 +1 sama-sama mencapai jumlah 0 pada posisi 2, jadi pencarian dari sana pun sama. Simpan setiap hasil saat pertama kali diperoleh, lalu gunakan kembali.

Jumlah berjalan tetap berada di antara -S dan S, jadi geser nilainya sebesar S agar dapat digunakan sebagai indeks: memo[i][total + S]. Ada paling banyak n × (2S+1) state, sekitar 4 × 10^4 untuk 20 angka yang jumlahnya 1000, masing-masing dengan operasi konstan.

Algoritma

Hitung S = sum(nums) dan buat memo berukuran n × (2S+1) yang diisi dengan -1.
Di dalam count(i, total), kembalikan kasus dasar pada i == n seperti sebelumnya.
Jika memo[i][total + S] bernilai -1, isi dengan count(i+1, total + nums[i]) + count(i+1, total - nums[i]).
Kembalikan nilai yang tersimpan, lalu panggil count(0, 0).

def findTargetSumWays(nums, target):
    n = len(nums)
    whole = sum(nums)
    # memo[i][total + whole]: ways for nums[i:] from this running total, -1 while unknown
    memo = [[-1] * (2 * whole + 1) for _ in range(n)]

    def count(i, total):
        if i == n:
            return 1 if total == target else 0
        if memo[i][total + whole] == -1:
            memo[i][total + whole] = count(i + 1, total + nums[i]) + count(i + 1, total - nums[i])
        return memo[i][total + whole]

    return count(0, 0)

Hitung banyaknya subset yang jumlahnya sama dengan (S + target) / 2

Intuisi

Misalkan P adalah jumlah angka bertanda plus dan N adalah jumlah angka lainnya. Maka P - N = target dan P + N = S, sehingga 2P = S + target. Pilihan tanda berhasil tepat ketika jumlah subset yang bertanda plus adalah (S + target) / 2, dan setiap subset seperti itu mewakili satu pilihan tanda.

ways[s] menghitung jumlah subset dari angka yang sudah diproses yang jumlahnya s, dimulai dari ways[0] = 1. Untuk setiap angka x, subset yang jumlahnya s bisa saja tidak menyertakan x atau menambahkannya ke subset yang jumlahnya s - x. Iterasi dari s terbesar ke terkecil, agar ways[s - x] masih menyimpan nilainya sebelum x diproses dan tidak ada angka yang digunakan dua kali. Angka 0 menambahkan setiap entri ke dirinya sendiri, sehingga semua hitungan menjadi dua kali lipat: ini mewakili dua pilihan tanda untuk angka nol. Jumlahnya adalah n × goal penambahan, paling banyak 2 × 10^4.

Algoritma

Hitung S = sum(nums). Jika |target| > S atau S + target ganjil, kembalikan 0.
Tetapkan goal = (S + target) / 2, buat ways yang berisi goal + 1 angka nol, lalu tetapkan ways[0] = 1.
Untuk setiap x dalam nums, untuk s dari goal turun hingga x, tambahkan ways[s - x] ke ways[s].
Kembalikan ways[goal].

def findTargetSumWays(nums, target):
    whole = sum(nums)
    # plus - minus = target and plus + minus = whole, so plus = (whole + target) / 2
    if abs(target) > whole or (whole + target) % 2 == 1:
        return 0
    goal = (whole + target) // 2
    # ways[s]: how many subsets of the values seen so far add up to s
    ways = [0] * (goal + 1)
    ways[0] = 1
    for x in nums:
        # From the top down, so each value is used at most once
        for s in range(goal, x - 1, -1):
            ways[s] += ways[s - x]
    return ways[goal]

Jebakan dan kasus tepi

Melewatkan pemeriksaan paritas. Untuk [6, 3] dan target 4, (9 + 4) / 2 dibulatkan ke bawah menjadi 6, dan subset {6} menghasilkan 1, bukan 0.
Melewatkan pemeriksaan rentang. Untuk [1, 2, 3] dan target -10, (6 - 10) / 2 = -2, ukuran array negatif.
Mengisi ways dari bawah ke atas. Angka kemudian bergabung dengan subset yang sudah menggunakannya: [1, 3] dengan target 2 melaporkan 2, bukan 1.
Menganggap nol sebagai satu pilihan. [0, 0, 0, 1, 0, 0] dengan target -1 memiliki 32 jawaban, satu untuk setiap pola tanda dari kelima angka nol.
Mengindeks memo menggunakan total berjalan negatif. Geser setiap total sebesar S, atau gunakan hash map.

Pertanyaan yang sering diajukan3

Bagaimana Target Sum berkaitan dengan masalah subset sum?

Angka-angka dengan tanda plus harus berjumlah (S + target) / 2, jadi jawabannya adalah jumlah subset dari nums dengan jumlah tersebut. DP untuk menghitung subset dengan jumlah tertentu dapat menyelesaikannya setelah kamu menambahkan dua pemeriksaan: nilainya harus berupa bilangan bulat, dan |target| tidak boleh lebih besar dari S.

Apa kompleksitas waktu dari Target Sum?

DP penghitungan subset berjalan dalam waktu O(n × S) dengan memori O(S), dengan S sebagai jumlah nums. Rekursi dengan memoization memiliki waktu yang sama, tetapi menggunakan tabel n × (2S+1). Mencoba setiap tanda membutuhkan O(2^n).

Apakah Target Sum dapat diselesaikan dengan hash map berisi jumlah berjalan?

Ya. Petakan setiap total berjalan yang dapat dicapai ke jumlah prefiks tanda yang mencapainya, dimulai dengan {0: 1}, lalu buat peta berikutnya dari total + x dan total - x untuk setiap angka. Jawabannya adalah jumlah pada target. Ini adalah rekursi yang di-memoisasi dan dijalankan ke depan, dengan waktu yang sama, O(n × S).

def findTargetSumWays(nums, target):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

nums = [2, 1, 1]
target = 2

Output yang diharapkan

Target Sum

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Coba kedua tanda untuk setiap angka

Memoisasikan berdasarkan posisi dan total berjalan

Hitung banyaknya subset yang jumlahnya sama dengan (S + target) / 2

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa