Subset Sum Problem
In LockedIn, we have a list of influencers and their respective follower counts. We want to find a subset of influencers whose total follower count is equal to a target number.
This problem is known as the Subset Sum Problem, which is an NP-hard problem. It asks the question, "Can we pick numbers from a list to add up to a target number?"
Assignment
Complete the subset_sum function.
It should take a list of integers nums and an integer target, and return True if there exists a subset of nums that adds up to target, and False otherwise. We'll use a recursive, brute-force approach to solve the problem. Brute-force just means we'll try every possible combination to see if any of them add up to the target.
Pseudocode: subset_sum(nums, target)
Inputs
nums: A list of integers representing the follower counts of influencers.target: The target sum we want to find a subset for.
Output
True if there exists a subset of nums that adds up to target. False otherwise.
Algorithm
- Call the helper function starting with the last index in
numsand return its result.
Pseudocode: find_subset_sum(nums, target, index)
Inputs
nums: A list of integers representing the follower counts of influencers.target: The target sum we want to find a subset for.index: The index of the current element we're considering.
Output
True if there exists a subset of nums that adds up to target. False otherwise.
Algorithm
- If the
targetis0, returnTrue. - If the index is less than
0and thetargetis not0, returnFalse. - If the number at the current index is greater than the
target, call the helper function with the sametargetbut with the index decremented by 1, andreturnthe result, we're done. - Otherwise, call the helper function with the same
targetand index decremented by 1, and save the result. - Also, call the helper function with the
targetreduced by the value of the current element and theindexdecremented by 1 - If either of these calls returns
True, returnTrue. Otherwise, returnFalse.