Target Sum trong C++

Cho mảng số không âm nums và target S. Gán dấu + hoặc - cho mỗi số sao cho tổng bằng S. Đếm số cách gán dấu.

Ví dụ: nums=[1,1,1,1,1], S=3 → output 5.

Giải thuật (DP memoization)

• Bảng dp[21][2001] khởi tạo -1 (vị trí dịch chuyển +1000 để xử lý âm).
• Hàm đệ quy solve(pos, tempSum, S):
  • Nếu pos == n: trả về tempSum == S.
  • Nếu dp[pos][tempSum+1000] != -1 trả về.
  • ans = solve(pos+1, tempSum - nums[pos], S) + solve(pos+1, tempSum + nums[pos], S).
  • Lưu và trả về.
• Gọi solve(0, 0, S).

Ví dụ code

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

class Solution {
public:
    int dp[21][2001];
    int solve(int pos, vector<int>& v, int tempSum, int S) {
        if (pos == v.size()) return tempSum == S;
        if (dp[pos][tempSum+1000] != -1) return dp[pos][tempSum+1000];
        int ans = solve(pos+1, v, tempSum - v[pos], S) + solve(pos+1, v, tempSum + v[pos], S);
        dp[pos][tempSum+1000] = ans;
        return ans;
    }
    int findTargetSumWays(vector<int>& nums, int S) {
        if (S > 1000) return 0;
        memset(dp, -1, sizeof(dp));
        return solve(0, nums, 0, S);
    }
};

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

Input

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

Output

5