Subset Sum Backtracking — When DP Is Too Slow

The recursion

boolean canSum(int[] nums, int target, int start) {
  if (target == 0) return true;
  if (target < 0 || start >= nums.length) return false;
  return canSum(nums, target - nums[start], start + 1)
      || canSum(nums, target, start + 1);
}

Pruning: sort descending

Try largest first. Fail faster on impossible branches.

Pruning: remaining sum

Track sum of remaining unused elements. If < target - current, prune.

Pruning: skip duplicates

If we skip an element, skip all copies of it. Prevents exploring same branch multiple times.