Question

2. There is a famous problem in computation called Subset Sum: Given a set S of n integers S = {a1, a2, a3, · · · , an} and a target value T, is it possible to find a subset of S that adds up to T? Consider the following example: S = {−17, −11, 22, 59} and the target is T = 65. (a) What are all the possible subsets I can make with S = {−17, −11, 22, 59}? What is the sum of each subset? Hint 1: Choosing no numbers is an option to get a sum of 0. Hint 2: Refer to exercise 4 (Knapsack problem) in the lecture notes. (b) How many subsets are possible with S? (c) Is there a subset of S that sums up to our target T = 65? (d) If I give you a set of 5 integers, how many possible subsets do I need to check? What if I give you n integers?

Answer 1