Problem Statement:
Given an integer array nums that may contain duplicates, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input:nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Example 2:
Input: nums = [0]
Output:[[],[0]]
Constraints:
1 <= nums.length <= 10-10 <= nums[i] <= 10
Approach:
- Sort the array to bring duplicates together.
- Use backtracking to explore all possible
subsets. - At each recursion step:
- Add the current subset (path) to the
result. - Loop through remaining elements starting from start.
- Skip duplicates: If the current element is the same as the previous one and not at the starting index of the loop, skip it.
- Add the current subset (path) to the
- Include the current element, recurse, then
backtrack(remove last element)./li>
Time Complexity:
Time Complexity = O(n*2n)
Space Complexity:
Space Complexity = O(n*2n) for recursion + O(n!) output storage.
Dry Run
Input: arr = [1, 2, 2]
Step 0: Start Function backtrackUniqueSubsets([1, 2, 2])
Sort arr → arr = [1, 2, 2]
Initialize:
result = []
path = []
Call backtrack([], 0)
→ Push [] → result = [[]]
Loop i = 0 → arr[0] = 1
path.push(1) → path = [1]
Call backtrack([1], 1)
→ Push [1] → result = [[], [1]]
Loop i = 1 → arr[1] = 2
path.push(2) → path = [1, 2]
Call backtrack([1, 2], 2)
→ Push [1, 2] → result = [[], [1], [1, 2]]
Loop i = 2 → arr[2] = 2
Condition: i > start && arr[i-1] === arr[i] → FALSE
path.push(2) → path = [1, 2, 2]
Call backtrack([1, 2, 2], 3)
→ Push [1, 2, 2] → result = [[], [1], [1, 2], [1, 2, 2]]
Loop ends (start = 3 >= n)
path.pop() → path = [1, 2]
Loop ends
path.pop() → path = [1]
Loop i = 2 → arr[2] = 2
Condition: i > start && arr[i-1] === arr[i] → TRUE (skip duplicate)
Loop ends
path.pop() → path = []
Loop i = 1 → arr[1] = 2
path.push(2) → path = [2]
Call backtrack([2], 2)
→ Push [2] → result = [..., [2]]
Loop i = 2 → arr[2] = 2
Condition: i > start && arr[i-1] === arr[i] → FALSE
path.push(2) → path = [2, 2]
Call backtrack([2, 2], 3)
→ Push [2, 2] → result = [..., [2, 2]]
Loop ends
path.pop() → path = [2]
Loop ends
path.pop() → path = []
Loop i = 2 → arr[2] = 2
Condition: i > start && arr[i-1] === arr[i] → TRUE (skip duplicate)
Loop ends
Step 3: End
Return result = [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
Output:
[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
Explanation: The array is sorted first so duplicates are adjacent. During backtracking, the condition
if (i > start && arr[i-1] === arr[i]) continue; ensures that duplicate elements at the same recursion depth are skipped, preventing duplicate subsets.
var subsetsWithDup = function(arr) {
let result = [];
arr.sort((a,b) => (a-b));
let backtrack = (path, start) => {
result.push([...path]);
for(let i=start; i start && arr[i-1] === arr[i])
continue;
path.push(arr[i]);
backtrack(path, i + 1);
path.pop();
}
}
backtrack([], 0)
return result;
};
def subsetsWithDup(arr):
arr.sort()
result = []
def backtrack(path, start):
result.append(path[:])
for i in range(start, len(arr)):
if i > start and arr[i] == arr[i - 1]:
continue
path.append(arr[i])
backtrack(path, i + 1)
path.pop()
backtrack([], 0)
return result
# Example usage
arr = [1, 2, 2]
print(subsetsWithDup(arr))
import java.util.*;
public class Main {
static void backtrack(int[] arr, List path, List> result, int start) {
result.add(new ArrayList<>(path));
for (int i = start; i < arr.length; i++) {
if (i > start && arr[i] == arr[i - 1]) continue;
path.add(arr[i]);
backtrack(arr, path, result, i + 1);
path.remove(path.size() - 1);
}
}
static List> subsetsWithDup(int[] arr) {
Arrays.sort(arr);
List> result = new ArrayList<>();
backtrack(arr, new ArrayList<>(), result, 0);
return result;
}
public static void main(String[] args) {
int[] arr = {1, 2, 2};
List> res = subsetsWithDup(arr);
for (List subset : res) {
System.out.println(subset);
}
}
}
void backtrack(vector& arr, vector& path, vector>& result, int start) {
result.push_back(path);
for (int i = start; i < arr.size(); i++) {
if (i > start && arr[i] == arr[i - 1]) continue;
path.push_back(arr[i]);
backtrack(arr, path, result, i + 1);
path.pop_back();
}
}
vector> subsetsWithDup(vector& arr) {
vector> result;
vector path;
sort(arr.begin(), arr.end());
backtrack(arr, path, result, 0);
return result;
}
int main() {
vector arr = {1, 2, 2};
vector> res = subsetsWithDup(arr);
for (auto &subset : res) {
for (int num : subset) cout << num << " ";
cout << endl;
}
}
int cmp(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
void backtrack(int* arr, int arrSize, int* path, int pathSize, int start) {
// Print current subset
for (int i = 0; i < pathSize; i++) printf("%d ", path[i]);
printf("\n");
for (int i = start; i < arrSize; i++) {
if (i > start && arr[i] == arr[i - 1]) continue;
path[pathSize] = arr[i];
backtrack(arr, arrSize, path, pathSize + 1, i + 1);
}
}
int main() {
int arr[] = {1, 2, 2};
int n = sizeof(arr) / sizeof(arr[0]);
qsort(arr, n, sizeof(int), cmp);
int path[n];
backtrack(arr, n, path, 0, 0);
return 0;
}
using System;
using System.Collections.Generic;
class Program {
static void Backtrack(int[] arr, List path, List> result, int start) {
result.Add(new List(path));
for (int i = start; i < arr.Length; i++) {
if (i > start && arr[i] == arr[i - 1]) continue;
path.Add(arr[i]);
Backtrack(arr, path, result, i + 1);
path.RemoveAt(path.Count - 1);
}
}
static IList> SubsetsWithDup(int[] arr) {
Array.Sort(arr);
var result = new List>();
Backtrack(arr, new List(), result, 0);
return result;
}
static void Main() {
int[] arr = {1, 2, 2};
var subsets = SubsetsWithDup(arr);
foreach (var subset in subsets) {
Console.WriteLine(string.Join(" ", subset));
}
}
}
