Question $310$ pts

Consider the following problem: We are given an array A$[1..$n$]$ of length $n$ where $n>1$ and a value $s>1.$

Find a maximum size subset of A whose sum is equal to $s.$ If no subset of A has sum $s,$ then print a

message "There is no subset with sum s$".$

Design an Exhaustive Search algorithm to solve this problem:

$(8$ pts$)$ Write the pseudo$-$code

$(2$ pts$)$ Analyze the worst$-$case running time.

Please note that for the exhaustive search is a brute force algorithm that must use one of the

combinatorial objects. Solutions which do not use exhaustive search will receive no credit.