Given a set of distinct integers, S, return all possible subsets.
- Elements in a subset must be in non-descending order.
- The solution set must not contain duplicate subsets.
If S =
[1,2,3], a solution is:
[ , , , [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]). 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?