Target Sum ใน C++

ตัวอย่าง: nums = [1,1,1,1,1], S = 3

วิธีที่เป็นไปได้ 5 วิธี:

+1+1+1+1+1 = 5 (ไม่ใช่)
+1+1+1+1-1 = 3 ✓
+1+1+1-1+1 = 3 ✓
+1+1-1+1+1 = 3 ✓
+1-1+1+1+1 = 3 ✓
-1+1+1+1+1 = 3 ✓

ผลลัพธ์: 5

อัลกอริทึม: DP with Memoization (Top-down)

แปลงปัญหา: ให้ P = ผลรวมตัวที่มี +, N = ผลรวมตัวที่มี -

P - N = S และ P + N = total_sum

→ 2P = S + total_sum → P = (S + total_sum) / 2

ปัญหาลดรูปเป็น: หาจำนวน subset ที่ผลรวม = P (Subset Sum Count)

แต่ตัวอย่างโค้ดใช้ Top-down DP โดยตรง:

State:

dp[pos][sum + offset] = จำนวนวิธีจากตำแหน่ง pos ถึงท้าย ที่ให้ผลรวมสะสม = sum

offset = 1000 (เพราะ sum อาจเป็นลบ เลขขั้ว ±1000)

Recurrence:

solve(pos, current_sum) = 
    if pos == n: return (current_sum == S) ? 1 : 0
    if memoized: return memo
    ans = solve(pos+1, current_sum + nums[pos]) + solve(pos+1, current_sum - nums[pos])
    memoize and return ans

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int dp[21][2001]; // n ≤ 20, sum range [-1000, 1000] → offset 1000
    
    int solve(int pos, vector<int>& nums, int curr_sum, int target) {
        if (pos == nums.size()) {
            return (curr_sum == target) ? 1 : 0;
        }
        if (dp[pos][curr_sum + 1000] != -1) 
            return dp[pos][curr_sum + 1000];
        
        int ans = solve(pos + 1, nums, curr_sum + nums[pos], target) 
                + solve(pos + 1, nums, curr_sum - nums[pos], target);
        
        dp[pos][curr_sum + 1000] = ans;
        return ans;
    }
    
    int findTargetSumWays(vector<int>& nums, int target) {
        if (target > 1000) return 0; // optimization
        memset(dp, -1, sizeof(dp));
        return solve(0, nums, 0, target);
    }
};

int main() {
    Solution ob;
    vector<int> v = {1, 1, 1, 1, 1};
    cout << ob.findTargetSumWays(v, 3) << endl;
    return 0;
}

Input

[1,1,1,1,1] 3

Output

5

ความซับซ้อน (Complexity)

• เวลา: O(n × sum_range) ≈ O(n × 2000) = O(n) เนื่องจาก sum_range คงที่
• พื้นที่: O(n × 2000) สำหรับ memo table

วิธีอื่น (Bottom-up Subset Sum): แปลงเป็นหา subset sum = (target + total)/2 ใช้ 1D DP O(n × target) ซึ่งเร็วกว่าและประหยัดพื้นที่มากกว่า