Back to course home
0% completed
Solution: Subset Sum
Problem Statement
Given a set of positive numbers, determine if there exists a subset whose sum is equal to a given number 'S'.
Example 1:
Input: {1, 2, 3, 7}, S=6
Output: True
The given set has a subset whose sum is '6': {1, 2, 3}
Example 2:
Input: {1, 2, 7, 1, 5}, S=10
Output: True
The given set has a subset whose sum is '10': {1, 2, 7}
Example 3:
Input: {1, 3, 4, 8}, S=6
Output: False
The given set does not have any subset whose sum is equal to '6'.
Basic Solution
This problem follows the 0/1 Knapsack pattern and is quite similar to
.....
.....
.....
Like the course? Get enrolled and start learning!