Subsets

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

• Time: O(n)
• Space: O(1)

public List<List<Integer>> subsets(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    subsetsDfs(ret, path, nums, 0);
    return ret;
}

private void subsetsDfs(List<List<Integer>> ret, List<Integer> path, int[] nums, int start) {
    ret.add(new ArrayList<>(path));
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        subsetsDfs(ret, path, nums, i + 1);
        path.remove(path.size() - 1);
    }
}

Subsets II

Given a collection of integers that might contain duplicates, S, return all possible subsets. The solution set must not contain duplicate subsets.

• Time: O(n)
• Space: O(1)

public List<List<Integer>> subsetsWithDup(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    subsetsWithDupDfs(ret, path, nums, 0);
    return ret;
}

private void subsetsWithDupDfs(List<List<Integer>> ret, List<Integer> path, int[] nums, int start) {
    ret.add(new ArrayList<>(path));
    for (int i = start; i < nums.length; i++) {
        if (i > start && nums[i] == nums[i - 1]) {
            continue;
        }
        path.add(nums[i]);
        subsetsWithDupDfs(ret, path, nums, i + 1);
        path.remove(path.size() - 1);
    }
}