# 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?