Subset Sum
Explore how to determine if a subset of given numbers sums to a target total using dynamic programming. Understand the naive recursive method first, then learn how to optimize it with memoization and tabulation techniques. Gain skills to improve algorithm efficiency and apply these patterns to related optimization problems.
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]