Chương trình đếm số cách gán dấu +/- để đạt target trong Python

Cho danh sách số không âm nums và số nguyên target. Gán dấu '+' hoặc '-' cho mỗi số sao cho tổng biểu thức bằng target. Đếm số cách gán dấu.

Ví dụ

nums = [2, 3, 3, 3, 2], target = 9

Cách 1: -2 + 3 + 3 + 3 + 2 = 9

Cách 2: +2 + 3 + 3 + 3 - 2 = 9

Kết quả: 2.

Quan sát quan trọng (Chuyển đổi thành Subset Sum)

Gọi P = tập số gán '+', N = tập số gán '-'.

sum(P) - sum(N) = target

sum(P) + sum(N) = total_sum

→ 2 * sum(P) = target + total_sum

→ sum(P) = (target + total_sum) / 2

Bài toán trở thành: đếm số subset có tổng = (target + total_sum) // 2.

Điều kiện

• (target + total_sum) phải chẵn.
• target <= total_sum.

Thuật toán (DP 1D - Coin Change biến thể)

1. W = (total_sum + target) // 2.
2. dp[w] = số cách đạt tổng w.
3. Khởi tạo dp[0] = 1.
4. Với mỗi num trong nums: duyệt w từ W xuống num, dp[w] += dp[w - num].

Triển khai Python

class Solution:
    def solve(self, nums, target):
        total = sum(nums)
        if (total + target) % 2 != 0 or target > total:
            return 0
        
        W = (total + target) // 2
        dp = [0] * (W + 1)
        dp[0] = 1
        
        for num in nums:
            for w in range(W, num - 1, -1):
                dp[w] += dp[w - num]
        
        return dp[W]

# Test
ob = Solution()
print(ob.solve([2, 3, 3, 3, 2], 9))  # Output: 2

Độ phức tạp

• Thời gian: O(n × W) với W = (sum + target)/2.
• Không gian: O(W).

Tương đương bài toán "Target Sum" (LeetCode 494).