Failing correctness test just because of the order of list


A : [ 12, 13 ]
Your function returned the following :
[] [12 ] [13 ] [12 13 ]
The expected returned value :
[] [12 ] [12 13 ] [13 ]
Quoting problem statement " The list is not necessarily sorted."
Please fix this issue


“Also, the subsets should be sorted in ascending ( lexicographic ) order.”

Only the input is not sorted slight_smile:


Yeah, this “lexicographic order” condition is a killer… it makes it sooo much more difficult that I’ve been stuck (or exceeding time limit when I loop and check for duplicates and sort it at each step…)


It’s a lousily specified problem - there are two common (and different) requirements in interviews/competitive programming:

(1) Generate subsets respecting the order of the input
(2) Generate subsets in lexicographic (alphabetical) order

By the way [], [12], [12, 13], [13] is correct - lexicographic implies that for each element in the subset, A[n,i] <= A[m,i] for all n < m and A[n,i] <= A[n,j] for all i < j. So [12, 13] comes before [13]. Think of it like a DFS rather than BFS.

It’s a good one to catch people out on, because if the interviewer asks for sorted output, you should ask if you can assume that the input is sorted. The computation time for a sort is negligible compared to the factorial complexity of generating all subsets, and as it’s unlikely to be the crux of the problem, it’s a one-liner (e.g. sort(A.begin(), A.end()) in virtually any language.

Note that if you solve the problem correctly, you should only need to sort the input once - sorting on each recursive call is redundant.


Before returning the result, you should sort the whole list using a custom comparator for List


just sort the list before making subsets.