Course4all

Subsets II

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Backtracking.

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

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionSubsets
Next Question →Letter Combinations of a Phone Number