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

https://leetcode.com/problems/subsets/

Consider example `[1,2,3]` returns `[], , , , [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) {
return;
}
for(int i = start; i < nums.length; 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) {