Give Me My Vector

Since number of subsets can be $2^{40}$ we cannot generate all of the subsets. But if we divide the input into two halves then, generate all subset of the halves, then number of subsets will be $2^{20}$, so we try a meet-in-the-middle approach.

When divided into two halves, a subset of the original input is created by merging subsets from the two groups. so if we generate two lists $A$, $B$ of all subset sums of the two halves. then subset sum of original input is created by adding two vectos from $A, B$. Now we can binary search for the $k$th lexicographically smallest vector. First we binary search on x coordinate (similar to two sum problem), then after fixing x, we can binary search for y coordinate (again similar to two sum problem). a naive implementation would be $2^{n/2}n^2$but by using two pointer approach it can be made into $2^{n/2}n$