Subsets I

Given a set of distinct integers, S, return all possible subsets.

Note:

  • Elements in a subset must be in non-descending order.
  • The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

(Java Code on github at the bottom of the post. )

My thoughts and solutions:

A good start point is to compare the Subsets of [1, 2, 3] with the Subsets of [2, 3] ([], [2], [3], [2, 3]). You will find that while retaining all elements in the latter, the former has additional elements which add the integer 1 to each element in the latter. So this may suggest a recursive algorithm:

Subsets(1,2,3,…,N) = Subsets(1,2,3,…,N-1) + adding N to each element of Subsets(1,2,3,…,N-1)

But there is no guarantee that the array is sorted. So be sure to sort it to ascending order first.

Code on github:

The only thing I’m concerned about is the running time. It seems like the algorithm is an exponential one? Or it should be exponential anyway?

Enhanced by Zemanta
Advertisements

5 thoughts on “Subsets I

  1. Consider a binary array with number of elements equal to the number of integers. Now each binary value correspond to an element being included (true) or excluded (false) from a given subset. Now simply start counter from 0 (empty set) and add 1 until you have reached 2^n (number of possible elements) – at each step change your counter into binary representation and this will enable you to create unique subset. So:
    [1,2,3]:
    000 – [],
    001 – [3],
    010 – [2],
    011 – [2, 3],
    etc.

    Since you have 2^n possibilities I think that algorithm has to be exponential. (To make it more optimal you don’t need counter but just operate on binary array). No need to sort it.

    1. Hi Marcin, thanks for the comment 🙂

      So in the binary representation, 1 means the integer is included? like 011 which means integer at index 1 and 2 are included so we get [2, 3]. If it is 100, then this means integer at index 0 is included so we get [1], right?

      But we need to know which bits are 1 each time? Am I missing something?

      1. Exactly, so if you have
        int c = 0; // it corresponds to [],
        while( c <= 2^n){
        get set which corresponds to binary representation of c;
        c++;
        }

        This loop will give you all possible subsets (from empty 0x0000..0, to full set 0x1111…11) all 1 + 2^n of them.

        The problem is if you have more elements in the starting set than integer max value (which in java at least is impossible), but then you can do a big array (in a language which will allow you to have array with more elements than Integer.MAX value) of booleans and increment it.

      2. Hmm, I’m just not so sure how we can get “the set which corresponds to c” in O(1) time. It seems like we have to iterate over n bits to get all indices with bit 1 and construct the set along the way, which is O(n) time.

        Do you have a faster solution for that? I really like your idea of bit operations 🙂

      3. No I don’t know any way to make it instantly. So it will be n * 2^n, that is still probably faster than adding element to previously built set of subsets (you have to keep old subsets and make copies of all of them (with one extra space for new value) – and here I think copies would be made in O(n) time as well)) You can run both and compare times for different sizes.

        But note that you probably don;t need to sort your input in your approach.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s