Course4all
Join us on telegram
Home/dsa/Backtracking/Subsets II

Subsets II

Master this topic with zero to advance depth.

Subsets II

Handling Duplicates

When the input array contains duplicates, the standard power set logic generates duplicate subsets. To avoid this, we must sort the array and skip identical elements during the recursion.

The Skip Condition

If nums[i] == nums[i-1] and we are at the same recursive level (not following the inclusion branch), we skip the current element to avoid repeating the same starting subset.

Generate all possible subsets of an integer array that may contain duplicates. Includes visual duplicate-skipping trace.

Medium

Examples

Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Approach 1

Level I: Backtracking with Sorting

Intuition

Sort and skip duplicates to ensure uniqueness.

Sort the array first. In the loop-based backtracking, if i > start and nums[i] == nums[i-1], we skip to the next iteration.

⏱ O(N * 2^N)💾 O(N)

Detailed Dry Run

nums=[1,2,2], start=1 1. i=1, pick nums[1]=2 -> subset [1,2] 2. i=2, nums[2]==nums[1], skip!
java
class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        backtrack(0, nums, new ArrayList<>(), res);
        return res;
    }
    private void backtrack(int start, int[] nums, List<Integer> curr, List<List<Integer>> res) {
        res.add(new ArrayList<>(curr));
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) continue;
            curr.add(nums[i]);
            backtrack(i + 1, nums, curr, res);
            curr.remove(curr.size() - 1);
        }
    }
}
← Previous QuestionSubsets
Next Question →Letter Combinations of a Phone Number