记得去重需要排序

都是从答案的角度：枚举第i位选哪个

在进入下一次递归前对重复元素进行判断

文章目录

• 带重复元素的子集型、排列型、组合型回溯
• • [90. 子集 II](https://leetcode.cn/problems/subsets-ii/)
  • [47. 全排列 II](https://leetcode.cn/problems/permutations-ii/)
  • [40. 组合总和 II](https://leetcode.cn/problems/combination-sum-ii/)

带重复元素的子集型、排列型、组合型回溯

90. 子集 II

难度中等1050

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10

class Solution {List> res;List cur;int[] nums;public List> subsetsWithDup(int[] nums) {Arrays.sort(nums); // 去重需要排序this.nums = nums;res = new ArrayList<>();cur = new ArrayList<>();dfs(0);return res;}public void dfs(int i){res.add(new ArrayList<>(cur));if(i == nums.length){return;}for(int j = i; j < nums.length; j++){// 我们要对同一树层使用过的元素进行跳过if(j > i && nums[j] == nums[j-1])continue;cur.add(nums[j]);dfs(j+1);cur.remove(cur.size()-1);}}
}

47. 全排列 II

难度中等1316

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],[1,2,1],[2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

class Solution {List> res;List cur;boolean[] visit;int[] nums;int n;public List> permuteUnique(int[] nums) {Arrays.sort(nums);res = new ArrayList<>();cur = new ArrayList<>();this.nums = nums;this.n = nums.length;visit = new boolean[n];dfs(0);return res;}public void dfs(int i){if(cur.size() == n){res.add(new ArrayList<>(cur));return;}for(int k = 0; k < n; k++){// visit[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过// visit[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过// 如果同⼀树层nums[i - 1]使⽤过则直接跳过if(k > 0 && nums[k] == nums[k-1] && visit[k-1] == false){// 如果要对树层中前一位去重，就用used[i - 1] == false，如果要对树枝前一位去重用used[i - 1] == true。// 对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高！continue;}if(!visit[k]){visit[k] = true;cur.add(nums[k]);dfs(i+1);cur.remove(cur.size()-1);visit[k] = false;}}}
}

40. 组合总和 II

难度中等1280

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

**注意：**解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

提示:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

class Solution {List> res;List cur;int[] candidates;int target;public List> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);res = new ArrayList<>();cur = new ArrayList<>();this.candidates = candidates;this.target = target;dfs(0, 0);return res;}public void dfs(int i, int sum){if(sum > target) return;if(sum == target){res.add(new ArrayList<>(cur));return;}for(int j = i; j < candidates.length; j++){if(j > i && candidates[j] == candidates[j-1])continue;cur.add(candidates[j]);dfs(j+1, sum + candidates[j]);cur.remove(cur.size()-1);}}
}