Subset Sum and All Subsets with Given Sum

Two-part phone-screen prompt: given an array and a target, first decide whether any subset sums to the target using DP with space optimized to O(target) and O(n * target) time; then return all subsets that sum to the target via backtracking in O(2^n) time, with a space-complexity analysis. Requirements Part 1 — Subset Sum (decision version): Given an array arr of non-negative integers and a target value target, determine whether any subset of the array sums exactly to target. Implement the dynamic-programming solution with the space optimization applied, bringing space complexity down to O(target). State the time complexity: O(n * target). Part 2 — All Subsets with Given Sum (enumeration follow-up): Return (or print) every subset of the array whose elements sum to target. Implement it with backtracking. State the time complexity, O(2^n), and analyze the space complexity of the recursion. Notes The round runs as an escalation: the decision version comes first with an explicit space-optimization requirement, then the interviewer moves to enumerating every qualifying subset with a different technique. Complexity analysis is requested explicitly at each step — time and space for both parts — rather than treated as an optional wrap-up.