Subsets II
Program for Printing all the Unique Subsets
You are given an array nums that contains integers, and some of these integers might be repeated. Your goal is to find all possible subsets (groups of numbers) that can be formed using the elements of this array.
A subset can include any combination of numbers, including no numbers at all (empty subset) or all the numbers in the array. However, your solution must ensure that no two subsets are the same. Even if the array contains duplicate numbers, the final list of subsets should not have duplicates.
You can arrange the subsets in any order when returning the result.
Output: [[],[1],[1,2],[1,1],[1,2,1],[2]]
Output: [[],[7], [7,7]]
Constraints:
- 1 <= nums.length <= 11
- -20 <= nums[i] <= 20
Program for Combinational Sum
Recommendation for Time and Space Complexity – Try to solve the problem with a time complexity of O(n * 2^n) or better, and a space complexity of O(n), where n is the size of the input array.
Hints for solving problems
Hint 1 :
A basic solution would involve using a hash set to store all subsets and remove duplicates. After generating the subsets, you can convert the hash set into a list. However, this approach requires extra space of O(2^n). A better way is to sort the array first, as this helps identify and skip duplicate subsets during recursion.
Hint 2 :
You can use backtracking to generate all subsets. If the input array has duplicate numbers, sorting the array helps handle them efficiently. For instance, in the array [1, 1, 2], sorting lets you process the first 1 and skip the second 1 when building subsets. This ensures all subsets are unique.
Hint 3 :
Start by sorting the input array. Then, use a recursive function to explore subsets by including or excluding each number as you go from left to right. To avoid duplicates, skip numbers that are the same as the previous one. Once all recursive paths are processed, return the list of unique subsets.
There are mainly 4 approach to solve this problem-
- Brute Force Method
- Backtracking(Pick/Not Pick) Method
- Backtracking Method
- Iteration Method
1. Brute Force Method
In this approach, all possible subsets of the array are generated, including duplicates. A hash set is then used to store only unique subsets by filtering out duplicates. While simple to implement, this method is inefficient in terms of both time and space.
- Time complexity: O(n* 2^n)
- Space complexity: O(2^n)
Code
class Solution {
set<vector<int>> res;
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
backtrack(nums, 0, {});
return vector<vector>(res.begin(), res.end());
}
void backtrack(vector<int>& nums, int i, vector<int> subset) {
if (i == nums.size()) {
res.insert(subset);
return;
}
subset.push_back(nums[i]);
backtrack(nums, i + 1, subset);
subset.pop_back();
backtrack(nums, i + 1, subset);
}
};
public class Solution {
Set<List<Integer>> res = new HashSet<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
backtrack(nums, 0, new ArrayList<>());
return new ArrayList<>(res);
}
private void backtrack(int[] nums, int i, List<Integer> subset) {
if (i == nums.length) {
res.add(new ArrayList<>(subset));
return;
}
subset.add(nums[i]);
backtrack(nums, i + 1, subset);
subset.remove(subset.size() - 1);
backtrack(nums, i + 1, subset);
}
}
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res = set()
def backtrack(i, subset):
if i == len(nums):
res.add(tuple(subset))
return
subset.append(nums[i])
backtrack(i + 1, subset)
subset.pop()
backtrack(i + 1, subset)
nums.sort()
backtrack(0, [])
return [list(s) for s in res]
class Solution {
constructor() {
this.res = new Set();
}
/**
* @param {number[]} nums
* @return {number[][]}
*/
subsetsWithDup(nums) {
nums.sort((a, b) => a - b);
this.backtrack(nums, 0, []);
return Array.from(this.res).map(subset => JSON.parse(subset));
}
/**
* @param {number[]} nums
* @param {number[]} subset
* @return {void}
*/
backtrack(nums, i, subset) {
if (i === nums.length) {
this.res.add(JSON.stringify(subset));
return;
}
subset.push(nums[i]);
this.backtrack(nums, i + 1, subset);
subset.pop();
this.backtrack(nums, i + 1, subset);
}
}
2. Backtracking(Pick/Not Pick) Method
This method uses recursion to explore all possible subsets by deciding at each step whether to include or exclude the current element. By sorting the input array and skipping duplicate elements, only unique subsets are generated efficiently.
- Time complexity: O(n* 2^n)
- Space complexity: O(n)
Code
class Solution {
vector<vector<int>> res;
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
backtrack(0, {}, nums);
return res;
}
void backtrack(int i, vector subset, vector& nums) {
if (i == nums.size()) {
res.push_back(subset);
return;
}
subset.push_back(nums[i]);
backtrack(i + 1, subset, nums);
subset.pop_back();
while (i + 1 < nums.size() && nums[i] == nums[i + 1]) {
i++;
}
backtrack(i + 1, subset, nums);
}
};
public class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
backtrack(0, new ArrayList<>(), nums);
return res;
}
private void backtrack(int i, List<Integer> subset, int[] nums) {
if (i == nums.length) {
res.add(new ArrayList<>(subset));
return;
}
subset.add(nums[i]);
backtrack(i + 1, subset, nums);
subset.remove(subset.size() - 1);
while (i + 1 < nums.length && nums[i] == nums[i + 1]) {
i++;
}
backtrack(i + 1, subset, nums);
}
}
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
def backtrack(i, subset):
if i == len(nums):
res.append(subset[::])
return
subset.append(nums[i])
backtrack(i + 1, subset)
subset.pop()
while i + 1 < len(nums) and nums[i] == nums[i + 1]:
i += 1
backtrack(i + 1, subset)
backtrack(0, [])
return res
class Solution {
/**
* @param {number[]} nums
* @return {number[][]}
*/
subsetsWithDup(nums) {
const res = [];
nums.sort((a, b) => a - b);
this.backtrack(0, [], nums, res);
return res;
}
/**
* @param {number} start
* @param {number[]} subset
* @param {number[]} nums
* @param {number[][]} res
* @return {void}
*/
backtrack(start, subset, nums, res) {
res.push([...subset]);
for (let i = start; i < nums.length; i++) { if (i > start && nums[i] === nums[i - 1]) {
continue;
}
subset.push(nums[i]);
this.backtrack(i + 1, subset, nums, res);
subset.pop();
}
}
}
3. Backtracking Method
This approach builds subsets recursively by extending the current subset one element at a time. Sorting the input array ensures that duplicate subsets are avoided by skipping consecutive duplicate elements during recursion.
- Time complexity: O(n* 2^n)
- Space complexity: O(n)
Code
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
backtrack(0, {}, nums);
return res;
}
void backtrack(int i, vector<int> subset, vector<int>& nums) {
res.push_back(subset);
for (int j = i; j < nums.size(); j++) { if (j > i && nums[j] == nums[j - 1]) {
continue;
}
subset.push_back(nums[j]);
backtrack(j + 1, subset, nums);
subset.pop_back();
}
}
};
public class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
backtrack(0, new ArrayList<>(), nums);
return res;
}
private void backtrack(int i, List<Integer> subset, int[] nums) {
res.add(new ArrayList<>(subset));
for (int j = i; j < nums.length; j++) { if (j > i && nums[j] == nums[j - 1]) {
continue;
}
subset.add(nums[j]);
backtrack(j + 1, subset, nums);
subset.remove(subset.size() - 1);
}
}
}
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = []
def backtrack(i, subset):
res.append(subset[::])
for j in range(i, len(nums)):
if j > i and nums[j] == nums[j - 1]:
continue
subset.append(nums[j])
backtrack(j + 1, subset)
subset.pop()
backtrack(0, [])
return res
class Solution {
constructor() {
this.res = [];
}
/**
* @param {number[]} nums
* @return {number[][]}
*/
subsetsWithDup(nums) {
nums.sort((a, b) => a - b);
this.backtrack(0, [], nums);
return this.res;
}
/**
* @param {number} i
* @param {number[]} subset
* @param {number[]} nums
* @return {void}
*/
backtrack(i, subset, nums) {
this.res.push([...subset]);
for (let j = i; j < nums.length; j++) { if (j > i && nums[j] === nums[j - 1]) {
continue;
}
subset.push(nums[j]);
this.backtrack(j + 1, subset, nums);
subset.pop();
}
}
}
4. Iteration Method
In this approach, subsets are built iteratively. Starting with an empty subset, for each element in the array, new subsets are created by adding the element to existing subsets. To handle duplicates, the input array is sorted, and new subsets are created only for elements that are not duplicates of the previous one.
- Time complexity: O(n* 2^n)
- Space complexity: O(1)
Code
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector> res = {{}};
int prevIdx = 0;
int idx = 0;
for (int i = 0; i < nums.size(); i++) { idx = (i >= 1 && nums[i] == nums[i - 1]) ? prevIdx : 0;
prevIdx = res.size();
for (int j = idx; j < prevIdx; j++) {
std::vector<int> tmp = res[j];
tmp.push_back(nums[i]);
res.push_back(tmp);
}
}
return res;
}
};
public class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
res.add(new ArrayList<>());
int prevIdx = 0;
int idx = 0;
for (int i = 0; i < nums.length; i++) { idx = (i >= 1 && nums[i] == nums[i - 1]) ? prevIdx : 0;
prevIdx = res.size();
for (int j = idx; j < prevIdx; j++) {
List<Integer> tmp = new ArrayList<>(res.get(j));
tmp.add(nums[i]);
res.add(tmp);
}
}
return res;
}
}
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = [[]]
prev_Idx = idx = 0
for i in range(len(nums)):
idx = prev_idx if i >= 1 and nums[i] == nums[i - 1] else 0
prev_idx = len(res)
for j in range(idx, prev_idx):
tmp = res[j].copy()
tmp.append(nums[i])
res.append(tmp)
return res
class Solution {
/**
* @param {number[]} nums
* @return {number[][]}
*/
subsetsWithDup(nums) {
nums.sort((a, b) => a - b);
const res = [[]];
let prevIdx = 0;
let idx = 0;
for (let i = 0; i < nums.length; i++) { idx = (i >= 1 && nums[i] === nums[i - 1]) ? prevIdx : 0;
prevIdx = res.length;
for (let j = idx; j < prevIdx; j++) {
const tmp = [...res[j]];
tmp.push(nums[i]);
res.push(tmp);
}
}
return res;
}
}
