Given a set of distinct integers, nums, return all possible subsets.

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);
	}
}
}