The Subset Sum problem asks whether a subset of given integers sums to a target. The backtracking solution explores inclusion/exclusion of each element, pruning branches where the remaining sum cannot be achieved. DP solves the decision problem in O(n × target) time.
void subsetSum(vector<int>& arr, int idx, int target, vector<int>& curr, vector<vector<int>>& res){
if(target==0){res.push_back(curr);return;}
for(int i=idx;i<arr.size();i++){
if(arr[i]>target) break;
curr.push_back(arr[i]);
subsetSum(arr,i+1,target-arr[i],curr,res);
curr.pop_back();
}
}For each element, decide to include it in the current subset or not. If included, subtract from the remaining target and recurse. If the target reaches 0, a valid subset is found.
Sort the array first. When iterating candidates, if arr[i] > remaining target, break immediately — no further elements can help (they are all larger). This prunes large portions of the search tree.
For the decision version (does any subset sum to target?), DP is more efficient: dp[j] = true if some subset sums to j. For each element, update dp[j] |= dp[j-arr[i]] backwards. O(n×target) time.
Quiz coming soon for this algorithm.