DP state dp[i][s] indicates whether sum s is achievable using first i items. Transition: take or skip current element. This converts exponential backtracking to pseudo-polynomial O(nW).
bool subsetSumDP(vector<int>& a, int W) {
int n = a.size();
vector<vector<bool>> dp(n + 1, vector<bool>(W + 1, false));
for (int i = 0; i <= n; i++) dp[i][0] = true;
for (int i = 1; i <= n; i++) {
for (int s = 1; s <= W; s++) {
dp[i][s] = dp[i - 1][s];
if (a[i - 1] <= s) dp[i][s] = dp[i][s] || dp[i - 1][s - a[i - 1]];
}
}
return dp[n][W];
}dp[i][s] answers whether sum s is possible using first i numbers.
Skip current item or include it if capacity allows.
Depends on numeric sum W, not just input length n.
Quiz coming soon for this algorithm.