给定一个可能具有重复数字的列表，返回其所有可能的子集。
在线评测地址：LintCode 领扣
样例 1：
输出：
[
[],
[0]
]样例 2：
输出：
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]解题思路
- 这道题我们需要使用dfs+回溯的方法来进行求解。
- 由于题目明确指出列表中可能有重复数字，所以我们在dfs的时候要进行剪枝。
算法 - 将数组进行升序排列。
- 定义一个递归方法 dfs，参数有：当前子集subset，当前子集长度k，返回结果res。 将当前子集添加到res中。 从 k 到 len(nums)-1 遍历索引i。 如果i != k并且nums[i] == nums[i - 1]，说明nums[i]是重复元素，所以我们跳过nums[i]。 将nums[i] 添加到当前子集subset。 进行下一层的递归搜索，继续向子集中添加元素，这时k要加一。 从 subset中删除nums[i]进行回溯。
举例分析
- 假设nums = [1, 2, 2']，递归树如图所示。树每深一层，子集的长度就加一。每个节点都是满足条件的子集，需要记录到结果res中。
- 其中标叉的地方进行了剪枝。由于数组中有两个2，所以如果两者在同一层，只保留第一个。
复杂度分析
- 时间复杂度：O(n∗2n)，其中n为nums的长度。生成所有子集，并复制到输出集合中。
- 空间复杂度：O(n∗2n)，其中n为nums的长度。存储所有子集，共 n个元素，每个元素都有可能存在或者不存在。
代码
public class Solution {
/**
* @param nums: A set of numbers.
* @return: A list of lists. All valid subsets.
*/
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
// 排序
Arrays.sort(nums);
// dfs搜索
Deque<Integer> subset = new ArrayDeque<>(nums.length);
dfs(nums, 0, subset, res);
return res;
}
private void dfs(int[] nums, int k, Deque<Integer> subset, List<List<Integer>> res) {
// 当前组合存入res
res.add(new ArrayList<>(subset));
// 为subset新增一位元素
for (int i = k; i < nums.length; ++i) {
// 剪枝
if (i != k && nums[i] == nums[i - 1]){
continue;
}
subset.addLast(nums[i]);
// 下一层搜索
dfs(nums, i + 1, subset, res);
// 回溯
subset.removeLast();
}
}
}
