Let $S$ be a set of $n$ positive integers each of which is less than $k.$ You arc

given set $S$ and a natural number $b,$ such that ASAO$((nk{)}^c)cb$ and goal $isto$ check $i$

there exist a subset $AofS$ such that the addition $of$ all the elements $in$ the

subset $Aisb.$ Give $an$ algorithm which has time complexity boundec

above $byO((nk{)}^c)$ for $anabsolute$ constant $c.$ Give detailed pseudo$-$cod

and the complexity analysis. $(Hint$: Note similarity with coin change

problem$)$