Subset Sum
Explore the Subset Sum problem by understanding how to identify subsets of numbers that sum to a given total. Learn to improve the naive recursive approach through top-down memoization and bottom-up tabulation using the 0 1 Knapsack dynamic programming pattern. Gain the skills to optimize time and space complexity for efficient solutions.
Statement
Given a set of positive numbers arr and a value total, determine if there exists a subset in the given set whose sum is equal to total. A subset can be an empty set, or it can either consist of some elements of the set or all the elements of the set.
Let’s say you are given a set = {1, 2, 3, 7} and a total = 6. The output will be TRUE as the subset = {1, 2, 3} adds up to make the desired total (1+2+3) = 6.
Constraints:
-
arr.length -
total -
arr[i]