Thursday, February 20, 2014

Subsets (Java)

Leetcode

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],
  []
]

Solution: DFS

For  subset of a given set, it must contain a [],
So we can initialize a result with [[]] as start point.  For example, given set [1,2,3]
We can build the result from [[]]-> [[],[1]]->[[],[1],[2],[1,2]]->[[],[1],[2], [1,2], [3], [1,3], [2,3], [1, 2,3]]