public class Solution {
//Test cases:
//[1,2,3,4,5,6]
//[]
//null
//[1]
//[1,2,...,1000]
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);
ArrayList<Integer> path = new ArrayList<Integer>();
subsetsHelper(S, 0, path, result);
return result;
}
private void subsetsHelper(int[] S, int pos, ArrayList<Integer> path,
ArrayList<ArrayList<Integer>> result) {
result.add(new ArrayList<Integer>(path));
for (int i = pos; i < S.length; i++) {
path.add(S[i]);
subsetsHelper(S, i + 1, path, result);//Attention:
//shall not set "pos + 1" as the second argument,
//because the logic is: after add the ith element,
//you can only add the elements which has index greater than i.
path.remove(path.size() - 1);
}
}
}
1.2 Subsets II (Unique Subsets)
Problem:Given a collection of integers that might contain duplicates, 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,2], a solution is:[ [2], [1], [1,2,2], [2,2], [1,2], [] ]
Solution:
(1) Use the Subsets template to solve this problem.
(2) The input is a collection, which will allow duplicate int, but the output should be unique, which means each int is allow to appear no more than once. Therefore, the second problem for us is to remove the duplicated ints.
(3) In which cases, there would be duplicated ints if we use subsets template to solve this problem?
e.g: input: [1, 2(first), 2(second), 2(third)]
output: [1, 2(first)] and [1, 2(second)], are "duplicated"
[1, 2(first), 2(second)] and [1, 2(second), 2(third)], are "duplicated"
Then, we got the pattern to prevent duplicated cases in out output, that is: When we try to get the next element from the sorted array and insert it into our result set, we should first check whether this element is duplicated. If it is, it will not be inserted, if there is an element equal to it and was not inserted into the result set.
(4) To implement this pattern, when we insert duplicated elements, our insertion should start from the first duplicated element in the sorted array, which means we will only allow [1, 2(first)], [1, 2(first), 2(second)] not allow cases like: [1, 2(second)].
Code:
public class Solution {
//Test cases:
//[]
//null
//[1,2,3]
//[1,2,2,3]
//[1]
//[2,2]
public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (num == null || num.length == 0) {
return result;
}
Arrays.sort(num);
ArrayList<Integer> path = new ArrayList<Integer>();
helper(num, result, path, 0);
return result;
}
private void helper(int[] num, ArrayList<ArrayList<Integer>> result,
ArrayList<Integer> path, int start) {
result.add(new ArrayList<Integer>(path));
for (int i = start; i < num.length; i++) {
if (i != start && num[i] == num[i - 1]) {
continue;
}
path.add(num[i]);
helper(num, result, path, i + 1);//calling itself: recursion
path.remove(path.size() - 1);//change the status back to how it was: backtracking } }
}
