刚才讲的标准子集问题输入的 nums 是没有重复元素的，但如果存在重复元素，怎么处理呢？
力扣第 90 题「子集 II」就是这样一个问题：
给你一个整数数组 nums，其中可能包含重复元素，请你返回该数组所有可能的子集。
函数签名如下：
List<List<Integer>> subsetsWithDup(int[] nums)比如输入 nums = [1,2,2]，你应该输出：
[ [],[1],[2],[1,2],[2,2],[1,2,2] ]
当然，按道理说「集合」不应该包含重复元素的，但既然题目这样问了，我们就忽略这个细节吧，仔细思考一下这道题怎么做才是正事。
就以 nums = [1,2,2] 为例，为了区别两个 2 是不同元素，后面我们写作 nums = [1,2,2']。
按照之前的思路画出子集的树形结构，显然，两条值相同的相邻树枝会产生重复：
[
[],
[1],[2],[2'],
[1,2],[1,2'],[2,2'],
[1,2,2']
]
你可以看到，[2] 和 [1,2] 这两个结果出现了重复，所以我们需要进行剪枝，如果一个节点有多条值相同的树枝相邻，则只遍历第一条，剩下的都剪掉，不要去遍历：
体现在代码上，需要先进行排序，让相同的元素靠在一起，如果发现 nums[i] == nums[i-1]，则跳过：
class Solution {
List<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> track = new LinkedList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
// 先排序，让相同的元素靠在一起
Arrays.sort(nums);
backtrack(nums, 0);
return res;
}
void backtrack(int[] nums, int start) {
// 前序位置，每个节点的值都是一个子集
res.add(new LinkedList<>(track));
for (int i = start; i < nums.length; i++) {
// 剪枝逻辑，值相同的相邻树枝，只遍历第一条
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
track.addLast(nums[i]);
backtrack(nums, i + 1);
track.removeLast();
}
}
}
回溯算法秒杀所有排列-组合-子集问题 | labuladong 的算法笔记
这段代码和之前标准的子集问题的代码几乎相同，就是添加了排序和剪枝的逻辑。
至于为什么要这样剪枝，结合前面的图应该也很容易理解，这样带重复元素的子集问题也解决了。
我们说了组合问题和子集问题是等价的，所以我们直接看一道组合的题目吧，这是力扣第 40 题「组合总和 II」：
给你输入 candidates 和一个目标和 target，从 candidates 中找出中所有和为 target 的组合。
candidates 可能存在重复元素，且其中的每个数字最多只能使用一次。
说这是一个组合问题，其实换个问法就变成子集问题了：请你计算 candidates 中所有和为 target 的子集。
所以这题怎么做呢？
对比子集问题的解法，只要额外用一个 trackSum 变量记录回溯路径上的元素和，然后将 base case 改一改即可解决这道题：
class Solution {
List<List<Integer>> res = new LinkedList<>();
// 记录回溯的路径
LinkedList<Integer> track = new LinkedList<>();
// 记录 track 中的元素之和
int trackSum = 0;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
if (candidates.length == 0) {
return res;
}
// 先排序，让相同的元素靠在一起
Arrays.sort(candidates);
backtrack(candidates, 0, target);
return res;
}
// 回溯算法主函数
void backtrack(int[] nums, int start, int target) {
// base case，达到目标和，找到符合条件的组合
if (trackSum == target) {
res.add(new LinkedList<>(track));
return;
}
// base case，超过目标和，直接结束
if (trackSum > target) {
return;
}
// 回溯算法标准框架
for (int i = start; i < nums.length; i++) {
// 剪枝逻辑，值相同的树枝，只遍历第一条
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
// 做选择
track.add(nums[i]);
trackSum += nums[i];
// 递归遍历下一层回溯树
backtrack(nums, i + 1, target);
// 撤销选择
track.removeLast();
trackSum -= nums[i];
}
}
}