Subset
Given a set of distinct integers, return all possible subsets.
Example
If S = [1,2,3]
, a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
Note
Elements in a subset must be in non-descending order.
For Question I: The solution set must not contain duplicate subsets. For Question II: The solution set may contain duplicate subsets.
Solution
// Question I:
public class Solution {
/**
* Recursive method, backtracking with a boolean array
**/
public ArrayList<ArrayList<Integer>> subsets(int[] num) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if(num == null || num.length == 0)
return result;
ArrayList<Integer> list = new ArrayList<Integer>();
Arrays.sort(num);
subsetsHelper(result, list, num, 0);
return result;
}
private void subsetsHelper(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> list, int[] num, int pos) {
result.add(new ArrayList<Integer>(list));
for (int i = pos; i < num.length; i++) {
list.add(num[i]);
subsetsHelper(result, list, num, i + 1);
list.remove(list.size() - 1);
}
}
/**
* Iterate method, a loop and retreve the value in original list and generate new value with insert it
**/
public ArrayList<ArrayList<Integer>> subsets(int[] num) {
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
if(num == null || num.length == 0)
return res;
ArrayList<Integer> list = new ArrayList<Integer>();
Arrays.sort(num);
res.add(list);
for(int i = 0; i < num.length; i++) {
int size = res.size();
for(int j = 0; j < size; j++) {
list = new ArrayList<>(res.get(j));
list.add(num[i]);
res.add(list);
}
}
return res;
}
}
// Question II:
public class Solution {
public ArrayList<ArrayList<Integer>> subsetsWithDup(ArrayList<Integer> num) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if(num == null || num.size() == 0) {
return result;
}
ArrayList<Integer> list = new ArrayList<Integer>();
Collections.sort(num);
subsetsHelper(result, list, num, 0);
return result;
}
private void subsetsHelper(ArrayList<ArrayList<Integer>> result,
ArrayList<Integer> list, ArrayList<Integer> num, int pos) {
result.add(new ArrayList<Integer>(list));
for (int i = pos; i < num.size(); i++) {
if(i > pos && num.get(i) == num.get(i-1))
continue;
list.add(num.get(i));
subsetsHelper(result, list, num, i + 1);
list.remove(list.size() - 1);
}
}
}