LeetCode 90: Subsets II (Backtracking with Level Dedup)
LeetCode 90BacktrackingDedupSortingToday we solve LeetCode 90 - Subsets II.
Source: https://leetcode.com/problems/subsets-ii/
English
Problem Summary
Given an integer array nums that may contain duplicates, return all possible subsets (the power set), without duplicate subsets.
Key Insight
Sort first, then in each DFS level skip repeated values that appear at the same depth. This keeps one representative branch for each value choice per level.
Brute Force and Limitations
Brute-force generate all 2^n subsets and deduplicate with a set of serialized arrays. It works, but introduces extra hash overhead and messy encoding logic.
Optimal Algorithm Steps (Sort + Backtracking + Level Dedup)
1) Sort nums.
2) DFS(start): append current path to answer.
3) Iterate i from start to end.
4) If i > start and nums[i] == nums[i-1], skip it (same-level duplicate).
5) Choose nums[i], recurse with i + 1, then backtrack.
Complexity Analysis
Time: O(n * 2^n) in the worst case (output-sensitive).
Space: O(n) recursion stack (excluding output).
Common Pitfalls
- Using i > 0 for skip condition (wrong scope), which incorrectly drops valid branches.
- Forgetting to sort before duplicate checks.
- Using global "used" logic from permutations; subsets need per-level dedup, not per-path dedup.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
backtrack(nums, 0, new ArrayList<>(), ans);
return ans;
}
private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> ans) {
ans.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++) {
if (i > start && nums[i] == nums[i - 1]) continue;
path.add(nums[i]);
backtrack(nums, i + 1, path, ans);
path.remove(path.size() - 1);
}
}
}func subsetsWithDup(nums []int) [][]int {
sort.Ints(nums)
ans := make([][]int, 0)
path := make([]int, 0)
var dfs func(start int)
dfs = func(start int) {
cur := append([]int(nil), path...)
ans = append(ans, cur)
for i := start; i < len(nums); i++ {
if i > start && nums[i] == nums[i-1] {
continue
}
path = append(path, nums[i])
dfs(i + 1)
path = path[:len(path)-1]
}
}
dfs(0)
return ans
}class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
vector<int> path;
dfs(nums, 0, path, ans);
return ans;
}
void dfs(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& ans) {
ans.push_back(path);
for (int i = start; i < (int)nums.size(); i++) {
if (i > start && nums[i] == nums[i - 1]) continue;
path.push_back(nums[i]);
dfs(nums, i + 1, path, ans);
path.pop_back();
}
}
};class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums.sort()
ans = []
path = []
def dfs(start: int) -> None:
ans.append(path[:])
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue
path.append(nums[i])
dfs(i + 1)
path.pop()
dfs(0)
return ansvar subsetsWithDup = function(nums) {
nums.sort((a, b) => a - b);
const ans = [];
const path = [];
const dfs = (start) => {
ans.push([...path]);
for (let i = start; i < nums.length; i++) {
if (i > start && nums[i] === nums[i - 1]) continue;
path.push(nums[i]);
dfs(i + 1);
path.pop();
}
};
dfs(0);
return ans;
};中文
题目概述
给定一个可能包含重复元素的数组 nums，返回所有子集（幂集），并且结果中不能出现重复子集。
核心思路
先排序，再在同一层递归中跳过重复值。这样每一层对于同值只展开一次分支，天然避免重复子集。
基线解法与不足
基线可先枚举全部 2^n 子集，再用集合去重。虽然可行，但会增加序列化与哈希开销，逻辑也不够干净。
最优算法步骤（排序 + 回溯 + 同层去重）
1）先对 nums 排序。
2）定义 DFS(start)：先把当前路径加入答案。
3）循环 i 从 start 到末尾。
4）若 i > start 且 nums[i] == nums[i-1]，跳过（同层重复）。
5）选择 nums[i]，递归 i+1，回溯撤销选择。
复杂度分析
时间复杂度：最坏 O(n * 2^n)（与输出规模相关）。
空间复杂度：O(n) 递归栈（不含答案存储）。
常见陷阱
- 把去重条件写成 i > 0，会错误跳过跨层分支。
- 没排序就做相邻去重判断。
- 套用全局 used[] 的排列模板，子集问题更适合“同层去重”。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
backtrack(nums, 0, new ArrayList<>(), ans);
return ans;
}
private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> ans) {
ans.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++) {
if (i > start && nums[i] == nums[i - 1]) continue;
path.add(nums[i]);
backtrack(nums, i + 1, path, ans);
path.remove(path.size() - 1);
}
}
}func subsetsWithDup(nums []int) [][]int {
sort.Ints(nums)
ans := make([][]int, 0)
path := make([]int, 0)
var dfs func(start int)
dfs = func(start int) {
cur := append([]int(nil), path...)
ans = append(ans, cur)
for i := start; i < len(nums); i++ {
if i > start && nums[i] == nums[i-1] {
continue
}
path = append(path, nums[i])
dfs(i + 1)
path = path[:len(path)-1]
}
}
dfs(0)
return ans
}class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
vector<int> path;
dfs(nums, 0, path, ans);
return ans;
}
void dfs(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& ans) {
ans.push_back(path);
for (int i = start; i < (int)nums.size(); i++) {
if (i > start && nums[i] == nums[i - 1]) continue;
path.push_back(nums[i]);
dfs(nums, i + 1, path, ans);
path.pop_back();
}
}
};class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums.sort()
ans = []
path = []
def dfs(start: int) -> None:
ans.append(path[:])
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue
path.append(nums[i])
dfs(i + 1)
path.pop()
dfs(0)
return ansvar subsetsWithDup = function(nums) {
nums.sort((a, b) => a - b);
const ans = [];
const path = [];
const dfs = (start) => {
ans.push([...path]);
for (let i = start; i < nums.length; i++) {
if (i > start && nums[i] === nums[i - 1]) continue;
path.push(nums[i]);
dfs(i + 1);
path.pop();
}
};
dfs(0);
return ans;
};
Comments