Sponsored
Sponsored
Use these hints if you're stuck. Try solving on your own first.
The naive solution is to check all possible subsequences. This works in O(2^n).
Divide the array into two parts of nearly is equal size.
Consider all subsets of one part and make a list of all possible subset sums and sort this list.
Consider all subsets of the other part, and for each one, let its sum = x, do binary search to get the nearest possible value to goal - x in the first part.