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?