Tag Archives: Subsets

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