I am expecting an answer in Java 8 with code and a detailed description with time complexity.

1h $43 \mathrm{~m}$ left มี ALL 1 2 3 4 3. Code Question 2 Amazon Shopping has $n$ items in inventory. Each item has a rating that may be negative. The team wants to work on an algorithm that will suggest combinations of these items that customers might buy, or, combos for short. A combo is defined as a subset of the given $n$ items. The total popularity of a combo is the sum of the popularities of the individual items in the combo. Design an algorithm that can find the $k$ combos with the highest popularities. Two combos are considered different if they have a different subset of items. Return an array of $k$ integers where the $i^{\text {th }}$ denotes the popularity of $i^{\text {th }}$ best combo. Combos should be returned arranged best to worst. Note: You can have an empty subset as a combo as well. The popularity for such a subset is 0 . Example \[ n=3 \] \[ \begin{array}{l} \text { popularity }=[3,5,-2] \\ k=3 \end{array} \] All possible popularities of combos are $0,3,5,-2,8,3,1,6$. The best three combos have popularities 8,6 , and 5 . The answer is $[8,6,5]$. Function Description Complete the function bestCombos in the editor below. bestCombos has the following parameters: int popularity[n]: popularity[i] denotes the popularity of $i^{\text {th }}$ item $(0 \leq i<n)$. int $k$ : the number of best combos to return Returns int[/k]: the popularities of the best $k$ combos, in decreasing order Constraints

1h $43 \mathrm{~m}$ left Returns H int [k]: the popularities of the best $k$ combos, in decreasing order ALL Constraints - $1 \leq n \leq 10^{5}$ - $-10^{9} \leq$ popularity $[i] \leq 10^{9}$ - $1 \leq k \leq \min \left(2000,2^{n}\right)$ 1 Input Format For Custom Testing 2 The first line contains an integer, $n$, the number of elements in popularity. Each line $i$ of the $n$ subsequent lines (where $0 \leq i<n$ ) contains an 3 integer, popularity [i]. The next line contains an integer, $k$. 4 Sample Case 0 Sample Input For Custom Testing STDIN Function $4 \rightarrow$ popularity [] size $n=4$ $1 \rightarrow$ popularity $=[1,2,3,1000]$ 3 1000 $4 \rightarrow k=4$ Sample Output \[ \begin{array}{l} 1006 \\ 1005 \\ 1004 \\ 1003 \end{array} \] Explanation All items can be included in a combo since $k$ equals the number of items. The second, third and fourth highest popularity is

1806 1005 1004 1003 Explanation All items can be included in a combo since $k$ equals the number of items. The second, third and fourth highest popularity is obtained by making combo of items with popularity $=\{2,3$, $1000\},\{1,3,1000\}$ and $\{1,2,1000\}$ respectively. Hence the answer is [1006, 1005, 1004, 1003]. 4 Sample Case 1 Sample Input For Custom Testing \[ \begin{array}{ll} \text { STDIN } & \text { FUNCTION } \\ \hdashline 5 & \rightarrow \text { popularity }[] \text { size } n=5 \\ 0 & \rightarrow \text { popularity }=[0,0,0,0,0] \\ 0 \\ 0 & \\ 0 \\ 0 \\ 3 & \rightarrow k=3 \end{array} \] Sample Output 0 0 0 Explanation The answer is $[0,0,0]$ as all have 0 popularity.