84. Subsets II

Sort so equal numbers are adjacent, then during backtracking skip a value that equals its left neighbor at the same recursion depth — that branch was already taken.

The duplicate problem

Plain subset backtracking would emit [2] twice if nums has two 2's. Sorting groups equal values together, and the rule 'at a given start, skip index i if nums[i] == nums[i-1] and i > start' prevents choosing the same value twice as the first pick of a level — which is exactly what creates duplicate subsets.

Walk-through

1. Sort nums.
2. Backtrack from index start, recording the current path as a subset at every node.
3. For i in [start, n): if i > start and nums[i] == nums[i-1], skip. Otherwise include nums[i], recurse from i+1, then undo.

Worked example

nums = [1,2,2] → sorted [1,2,2]:

• [], [1], [1,2], [1,2,2], [2], [2,2].
• The second [2] branch (from the duplicate 2) is skipped because i > start and nums[i]==nums[i-1].

Result: [[],[1],[1,2],[1,2,2],[2],[2,2]].

Complexity

• Time: O(n · 2^n) — up to 2^n subsets, each up to length n to copy.
• Space: O(n) recursion depth (excluding output).

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
        res.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]);
            backtrack(nums, i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }
}