子集 - 三种形式-拓冰建站

无重不可复选，可重不可复选，无重可复选

78. 子集 - 元素无重不可复选

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

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

题解

通过保证元素之间的相对顺序不变来防止出现重复的子集

注意：把根节点当作第 0 层，第 n 层的所有节点就是节点数目为 n 的所有子集。

使用 start 避免产生重复的子集。
使用 track 记录根到每个节点的路径。
前序位置收集所有子集。

public List<List<Integer>> res = new LinkedList<>(); // 结果
public LinkedList<Integer> track = new LinkedList<>(); // 记录路径
public List<List<Integer>> subsets(int[] nums) {backtrack(nums, 0);return res;
}
// 回溯算法，遍历子集问题的回溯树
public void backtrack(int[] nums, int start) {// 前序遍历，记录所有节点的值，每个节点的值都是一个子集res.add(new LinkedList<>(track));// 回溯框架for (int i = start; i < nums.length; i++) { //当 start == nums.length 时，叶子节点的值会被装入 res，但 for 循环不会执行，也就结束了递归。// 做选择track.add(nums[i]);// 只选择start之后的值，通过 start 参数控制树枝的遍历，避免产生重复的子集backtrack(nums, i + 1);// 撤销选择track.removeLast();}
}

90. 子集 II - 元素可重不可复选

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

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

题解

剪枝

排序让相同元素在一起
如果发现重复值： nums[i] == nums[i-1]，跳过

public List<List<Integer>> res = new LinkedList<>(); // 结果
public LinkedList<Integer> track = new LinkedList<>(); // 记录路径
public List<List<Integer>> subsetsWithDup(int[] nums) {// 先排序，让相同的元素靠在一起Arrays.sort(nums);backtrack(nums, 0);return res;
}
/*** 剪枝，值相同的相邻树枝(跳过)，只遍历第一个*/
public 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.add(nums[i]);backtrack(nums, i + 1);track.removeLast();}
}

子集 III - 元素无重可复选

通过start参数，控制树枝的遍历

start = start，下一层回溯树，可以选自己（一个元素可以无限次使用）
start = start + 1，下一层回溯树，不可以选自己(一个元素只使用一次)

public List<List<Integer>> res = new LinkedList<>(); // 记录结果
public LinkedList<Integer> track = new LinkedList<>(); // 记录回溯路径
public List<List<Integer>> subsets(int[] nums) {backtrack(nums, 0);return res;
}
// 回溯算法
public void backtrack(int[] nums, int start) {// 前序位置，每个节点的值都是一个子集if (track.size() == nums.length) {res.add(new LinkedList<>(track));return;}for (int i = start; i < nums.length; i++) {track.add(nums[i]);// 通过start参数，控制树枝的遍历// start = start，下一层回溯树，可以选自己（一个元素可以无限次使用）// start=start+1，下一层回溯树，不可以选自己(一个元素只使用一次)backtrack(nums, i);track.removeLast();}
}