Description:
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.
Examples:
Example 1:
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Example 2:
Input: nums = [0]
Output: [[],[0]]Solution in Python:
To solve the problem of generating all possible subsets (the power set) of an integer array nums that may contain duplicates, we can use a backtracking approach.
Step-by-step explanation of the solution:
Sort the Input Array: Sorting the array helps us easily handle duplicates, as duplicates will be adjacent in the sorted array.
Use Backtracking: We’ll use a recursive backtracking approach to generate subsets. We maintain a temporary list (temp) that represents the current subset being constructed, and we use a result list (res) to store all unique subsets.
Avoid Duplicates: During the recursion, to avoid adding duplicate subsets, we skip over duplicate elements. This is done by checking if the current element is the same as the previous one and only processing it if it’s the first time we encounter it at this level of recursion.
Recursive Function: The recursive function will explore two possibilities at each step:
- Including the current element in the subset.
- Not including the current element and moving to the next.
Python
from typing import List
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
def backtrack(start: int, temp: List[int]):
# Add the current subset to the result
res.append(temp[:])
# Explore further elements to include in the subset
for i in range(start, len(nums)):
# If the current element is the same as the previous one, skip it to avoid duplicates
if i > start and nums[i] == nums[i - 1]:
continue
# Include nums[i] in the current subset
temp.append(nums[i])
# Move on to the next element
backtrack(i + 1, temp)
# Backtrack, remove the last element from the current subset
temp.pop()
# Sort the array to handle duplicates easily
nums.sort()
res = []
backtrack(0, [])
return resExplanation of the Code:
- Sorting the Array:
nums.sort()- This sorts the input array to bring duplicates together.
- Backtrack Function:
def backtrack(start: int, temp: List[int])start: The index to start from in the array for generating subsets.temp: A temporary list that stores the current subset.
- Appending Current Subset:
res.append(temp[:])- We add a copy of the current subset (
temp[:]) to the result list (res).
- We add a copy of the current subset (
- Loop to Generate Subsets:
for i in range(start, len(nums))- We iterate over the elements starting from the
startindex.
- We iterate over the elements starting from the
- Skipping Duplicates:
if i > start and nums[i] == nums[i - 1]: continue- This condition ensures we skip processing for duplicate elements at the same recursion level.
- Include Current Element:
temp.append(nums[i])- We include the current element in the subset.
- Recursive Call:
backtrack(i + 1, temp)- We recursively call
backtrackto generate further subsets including the current element.
- We recursively call
- Backtrack Step:
temp.pop()- We remove the last element to backtrack and try the next possibility.
The res list will contain all unique subsets of the input array nums. This solution ensures no duplicate subsets are included due to the sorting and the check for duplicates during the recursion.
Solution in Javascript:
JavaScript
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsetsWithDup = function(nums) {
// Define the result array to store all subsets
const res = [];
// Sort the array to handle duplicates easily
nums.sort((a, b) => a - b);
/**
* Backtracking function to generate subsets
* @param {number} start - The starting index for generating subsets
* @param {number[]} temp - The current subset being constructed
*/
function backtrack(start, temp) {
// Add the current subset (make a copy of temp) to the result
res.push([...temp]);
// Iterate over the elements starting from 'start' index
for (let i = start; i < nums.length; i++) {
// If the current element is the same as the previous one, skip it to avoid duplicates
if (i > start && nums[i] === nums[i - 1]) continue;
// Include nums[i] in the current subset
temp.push(nums[i]);
// Move on to the next element
backtrack(i + 1, temp);
// Backtrack: remove the last element from the current subset
temp.pop();
}
}
// Start backtracking with an empty subset
backtrack(0, []);
// Return the result array containing all subsets
return res;
};Solution in Java:
Java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
// Sort the input array to handle duplicates easily
Arrays.sort(nums);
// List to store all subsets
List<List<Integer>> res = new ArrayList<>();
// Backtracking function to generate subsets
backtrack(nums, 0, new ArrayList<>(), res);
// Return the list of subsets
return res;
}
/**
* Backtracking function to generate subsets
* @param nums The input array
* @param start The starting index in the input array
* @param temp The current subset being constructed
* @param res The list of all subsets
*/
private void backtrack(int[] nums, int start, List<Integer> temp, List<List<Integer>> res) {
// Add the current subset to the result
res.add(new ArrayList<>(temp));
// Iterate over the elements starting from 'start' index
for (int i = start; i < nums.length; i++) {
// If the current element is the same as the previous one, skip it to avoid duplicates
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
// Include nums[i] in the current subset
temp.add(nums[i]);
// Recursively generate subsets starting from the next index
backtrack(nums, i + 1, temp, res);
// Backtrack: remove the last element to backtrack
temp.remove(temp.size() - 1);
}
}
}Solution in C#:
C#
public class Solution {
public IList<IList<int>> SubsetsWithDup(int[] nums) {
// Sort the input array to handle duplicates easily
Array.Sort(nums);
// List to store all subsets
IList<IList<int>> res = new List<IList<int>>();
// Backtracking function to generate subsets
Backtrack(nums, 0, new List<int>(), res);
// Return the list of subsets
return res;
}
/**
* Backtracking function to generate subsets
* @param nums The input array
* @param start The starting index in the input array
* @param temp The current subset being constructed
* @param res The list of all subsets
*/
private void Backtrack(int[] nums, int start, List<int> temp, IList<IList<int>> res) {
// Add the current subset to the result
res.Add(new List<int>(temp));
// Iterate over the elements starting from 'start' index
for (int i = start; i < nums.Length; i++) {
// If the current element is the same as the previous one, skip it to avoid duplicates
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
// Include nums[i] in the current subset
temp.Add(nums[i]);
// Recursively generate subsets starting from the next index
Backtrack(nums, i + 1, temp, res);
// Backtrack: remove the last element to backtrack
temp.RemoveAt(temp.Count - 1);
}
}
}