Consider example [1,2,3] returns [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]
The problem is classic example of backtracking. If there is no duplicate element, the answer is simply 2^n, where n is the number of elements. This is because you have two choices for each element, either putting it into the subset or not. So all subsets for this no-duplicate set can be easily constructed.
public class SubSet {
public List> subsets(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> l = new ArrayList();
for (int i = 0; i <= nums.length; i++) {
subsets(nums, i, l, 0, new ArrayList());
}
return l;
}
private void subsets(int[] nums, int currLength, List<List<Integer>> l,
int start, List<Integer> curr) {
if (curr.size() == currLength) {
l.add(new ArrayList(curr));
return;
}
for(int i = start; i < nums.length; i++) {
curr.add(nums[i]);
subsets(nums, currLength, l, i+1, curr);
curr.remove(curr.size() - 1);
}
}
} The above code can further be optimized and done is fewer lines:
public class SubSet {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> l = new ArrayList();
subsets(nums, l, 0, new ArrayList());
return l;
}
private void subsets(int[] nums, List<List<Integer>> l, int start, List<Integer> curr) {
l.add(new ArrayList(curr));
for(int i=start; i < nums.length; i++) {
curr.add(nums[i]);
subsets(nums, l, i+1, curr);
curr.remove(curr.size() - 1);
}
}
}