Given a set {a, b, c, d}, its non-empty subsets in lexicographic order are as follows: {a, ab, abc, abcd, abd, ac, acd, ad, b, bc, bcd, bd, c, cd, d}
I found an O(N^2) method of finding the Nth lexicographically smallest subset here, but I was wondering if there was a faster way to do this.
I know that finding the Nth lexicographically smallest string can be reduced from O(N^2) time to O(N) time, which motivated me to ask this question about a similar reduction for subsets.
Please help, and thanks in advance!