โปรแกรมหาจำนวนวิธีจัดสัญลักษณ์ + - เพื่อให้ได้ค่าเป้าหมายใน Python

สมมติว่าเรามีรายการตัวเลขไม่ติดลบ nums และค่าเป้าหมาย target หาจำนวนวิธีวางเครื่องหมาย + หรือ - หน้าตัวเลขแต่ละตัว เพื่อให้ผลรวมเท่ากับ target

ตัวอย่าง

อินพุต: nums = [2, 3, 3, 3, 2], target = 9

เอาต์พุต: 2

วิธีที่ 1: -2 + 3 + 3 + 3 + 2 = 9

วิธีที่ 2: 2 + 3 + 3 + 3 - 2 = 9

ขั้นตอนการแก้ปัญหา

แปลงเป็นโจทย์ Subset Sum: ให้ P เป็นเซตตัวเลขที่มีเครื่องหมาย +, N เป็นเซตเครื่องหมาย -

sum(P) - sum(N) = target และ sum(P) + sum(N) = total

=> 2 * sum(P) = target + total ดังนั้น sum(P) = (target + total) / 2

ถ้า (total + target) % 2 != 0 หรือ target > total คืน 0

ใช้ DP นับจำนวน subset ที่รวมได้ W = (total + target) // 2:

1. dp1[0] = 1, dp2 เป็นอาร์เรย์ช่วย
2. สำหรับแต่ละ num ใน nums:
   • อัปเดต dp2[j] += dp1[j - num] สำหรับ j >= num
   • รวม dp1[j] += dp2[j] แล้วล้าง dp2
3. คืนค่า dp1[W]

การนำไปใช้ใน Python

class Solution:
    def solve(self, nums, target):
        s = sum(nums)
        if (s + target) % 2 != 0 or target > s:
            return 0
        W = (s + target) // 2
        dp1 = [0] * (W + 1)
        dp1[0] = 1
        dp2 = [0] * (W + 1)
        for i in range(len(nums)):
            for j in range(W + 1):
                if j >= nums[i]:
                    dp2[j] += dp1[j - nums[i]]
            for j in range(W + 1):
                dp1[j] += dp2[j]
                dp2[j] = 0
        return dp1[-1]

ob = Solution()
nums = [2, 3, 3, 3, 2]
target = 9
print(ob.solve(nums, target))

อินพุต

[2, 3, 3, 3, 2], 9

เอาต์พุต

2