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

If

**=***S*`[1,2,3]`

, a solution is:[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

**Understand the problem:**

As described in the problem, 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.

**Recursive Solution:**

public class Solution { public ArrayList<ArrayList<Integer>> subsets(int[] S) { ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); if (S == null || S.length == 0) return result; Arrays.sort(S); result.add(new ArrayList<Integer>()); ArrayList<Integer> temp = new ArrayList<Integer>(); subsetsHelper(S, 0, result, temp); return result; } private void subsetsHelper(int[] S, int start, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> temp) { if (start >= S.length) return; for (int i = start; i < S.length; i++) { temp.add(S[i]); result.add(new ArrayList<Integer>(temp)); subsetsHelper(S, i + 1, result, temp); temp.remove(temp.size() - 1); } } }

## No comments:

## Post a Comment