# All Subsets

Given a collection of integers that might contain duplicates, return all possible subsets.

## Code

``````ArrayList<ArrayList<Integer>> getSubset(int[] arr){
ArrayLIst<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> path = new ArrayList<Integer>();
Array.sort(arr);
subsetWithDup(0, arr, path, result);
return result;
}

void subsetWithDup(int index, int[] arr, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> result){
if (index == arr.length) return;
for (int i = index; i < arr.length; i++){
if (i != index && arr[i] == arr[i-1])
continue;
path.add(arr[i]);
result.add(new ArrayList<Integer>(path));
subsetWithDup(index + 1, arr, path, result);
path.remove(path.size()-1);
}
}
``````

``````public class Solution {
public List<List<Integer>> subsets(int[] S) {
return subsets_2(S);
}

public List<List<Integer>> subsets_1(int[] S) {
Arrays.sort(S);
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> path = new ArrayList<Integer>();
subsetsRe(S, 0, path, res);
return res;
}
void subsetsRe(int[] S, int start, List<Integer> path, List<List<Integer>> res) {
List<Integer> sub = new ArrayList<Integer>(path);
res.add(sub);
for (int i = start; i < S.length; ++i) {
path.add(S[i]);
subsetsRe(S, i + 1, path, res);
path.remove(path.size() - 1);
}
}

public List<List<Integer>> subsets_2(int[] S) {
Arrays.sort(S);
List<List<Integer>> res = new ArrayList<List<Integer>>();
res.add(new ArrayList<Integer>());
for (int i = 0; i < S.length; ++i) {
int sz = res.size();
for (int j = 0; j < sz; ++j) {
List<Integer> path = new ArrayList<Integer>(res.get(j));
path.add(S[i]);
res.add(path);
}
}
return res;
}
}
``````

``````public class Solution {
public List<List<Integer>> subsetsWithDup(int[] S) {
Arrays.sort(S);
List<List<Integer>> res = new ArrayList<List<Integer>>();
res.add(new ArrayList<Integer>());
int presz = 0;
for (int i = 0; i < S.length; ++i) {
int sz = res.size();
for (int j = 0; j < sz; ++j) {
if (i == 0 || S[i] != S[i-1] || j >= presz) {
List<Integer> path = new ArrayList<Integer>(res.get(j));
path.add(S[i]);
res.add(path);
}
}
presz = sz;
}
return res;
}
}
``````