please solve q4 c

4. (30 points) In this exercise, you will write and analyze a program that solves the subset sum problem (which is a special case of the 0/1 knapsack problem when w; = w). The problem receives as input a set of values S = {11.02...., Un} and an integer W. It then outputs a subset of S whose sum is equal to W. For example, if the input is S = {7,3,2,5,8) and W = 14 then it outputs {7.2,5} because 7 +2 +5 = 14. (a) (5 points) Write a program that solves the subset problem using brute force. That is, it checks every possible set of integers to check if they are equal to W. For the above example, it will check 7,3 then 7,2 then 7.3.2 and so on until it finds a solution. Measure the time needed to find the solution for any input of length n= 5 and n = 10. (b) (10 points) Write a program that attempts to solve the subset problem using a greedy approach where the greedy choice to choose the smallest integer in S less than the sum so far until W is reached. Using the example above, it will choose 2 first then add to it the next smallest integer 3 (to get 5) then add to it the next smallest integer 5 (to get 10) then we stop since adding 7 will make the sum exceed W = 14. Is your output optimal? (c) (15 points) Write a program that solves the subset problem using dynamic program- ming Your solution must use memoization as part of the implementation. Measure the time needed to find the solution for any input of length n = 5 and n = 10. Compare the time measured here against the brute force solution