一、组合
参考链接77. 组合 - 力扣（LeetCode）
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class Solution {
public List<List<Integer>> combine (int n, int k) {
List<List<Integer>> res = new ArrayList<>();
if (k <= 0 || n < k) {
return res;
}
Deque<Integer> path = new ArrayDeque<>();
dfs(n, k, 1, path, res);
return res;
}
private void dfs(int n, int k, int index, Deque<Integer> path, List<List<Integer>> res) {
//如果当前path的大小和 k相等，则将结果保存到ArrayList当中
if (path.size() == k) {
res.add(new ArrayList<>(path));
return;
}
// 剪枝优化 i <= n - (k - path.size()) + 1 背吧，归纳法
for (int i = index; i <= n - (k - path.size()) + 1; i++) {
path.addLast(i);
dfs(n, k, i + 1, path, res);
path.removeLast();
}
}
}
二、递增子序列
核心理解：set去重
set在dfs的实现的方式是 new HashSet<>()，而不是在函数外定义的set，每一次递归都会生成新的Set，
class Solution {
// 定义全局变量保存结果
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> findSubsequences(int[] nums) {
// idx 初始化为 -1，开始 dfs 搜索。
dfs(nums, -1, new ArrayList<>());
return res;
}
private void dfs(int[] nums, int idx, List<Integer> curList) {
// 只要当前的递增序列长度大于 1，就加入到结果 res 中，然后继续搜索递增序列的下一个值。
if (curList.size() > 1) {
res.add(new ArrayList<>(curList));
}
// 在 [idx + 1, nums.length - 1] 范围内遍历搜索递增序列的下一个值。
// 借助 set 对 [idx + 1, nums.length - 1] 范围内的数去重。
//注意 set是 数中每一层的 变量，到达下一层时又new了HashSet
Set<Integer> set = new HashSet<>();
for (int i = idx + 1; i < nums.length; i++) {
// 1. 如果 set 中已经有与 nums[i] 相同的值了，说明加上 nums[i] 后的所有可能的递增序列之前已经被搜过一遍了，因此停止继续搜索。
if (set.contains(nums[i])) {
continue;
}
set.add(nums[i]);
// 2. 如果 nums[i] >= nums[idx] 的话，说明出现了新的递增序列，因此继续 dfs 搜索（因为 curList 在这里是复用的，因此别忘了 remove 哦）
if (idx == -1 || nums[i] >= nums[idx]) {
curList.add(nums[i]);
dfs(nums, i, curList);
curList.remove(curList.size() - 1);
}
}
}
}
- 比如 4 7 3 2 1 7 … 这个数组，当curList遍历到 4 7 的时候，进入递归，一直遍历直到 出现 第二个7，这时候出现了 4 7 7 序列添加到结果中
- 回溯到 4 7 ，在当前层的for循环进行遍历，再次遍历到 第二个 7，判断set中有7，通过1我们知道 4 7 7 开头的数组组合我们在递归中已经将其实现，所以这一枝我们进行剪枝
- 回归set的作用，处理数组中出现相同值时 出现重复结果(也就是去重)
参考链接46. 全排列 - 力扣（LeetCode）
三、全排列
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<List<Integer>> permute(int[] nums) {
int len = nums.length;
// 使用一个动态数组保存所有可能的全排列
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}
//使用一个数组表示某个数是否已经被选过，选过为true，否则为false
boolean[] used = new boolean[len];
List<Integer> path = new ArrayList<>();
dfs(nums, len, 0, path, used, res);
return res;
}
//nums 当前数组，len 数组长度，depth表示深度，path 当前走过的路径，used 某个数字是否被选中， res 结果数组
private void dfs(int[] nums, int len, int depth,
List<Integer> path, boolean[] used,
List<List<Integer>> res) {
// 如果遍历到 深度 和 长度 相等表示所有数字都已经被选择过了
if (depth == len) {
res.add(path);
return;
}
// 在非叶子结点处，产生不同的分支，这一操作的语义是：在还未选择的数中依次选择一个元素作为下一个位置的元素，这显然得通过一个循环实现。 ****这段是重点核心代码，需要背
for (int i = 0; i < len; i++) {
if (!used[i]) {
path.add(nums[i]);
used[i] = true;
dfs(nums, len, depth + 1, path, used, res);
// 注意：下面这两行代码发生 「回溯」，回溯发生在从 深层结点 回到 浅层结点 的过程，代码在形式上和递归之前是对称的
used[i] = false;
path.remove(path.size() - 1);
}
}
}
public static void main(String[] args) {
int[] nums = {1, 2, 3};
Solution solution = new Solution();
List<List<Integer>> lists = solution.permute(nums);
System.out.println(lists);
}
}
四、全排列2
使用存在重复数字的数组来生成新的全排列数组，要求去重
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;
public class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
int len = nums.length;
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}
// 排序（升序或者降序都可以），排序是剪枝的前提
Arrays.sort(nums);
boolean[] used = new boolean[len];
// 使用 Deque 是 Java 官方 Stack 类的建议
Deque<Integer> path = new ArrayDeque<>(len);
dfs(nums, len, 0, used, path, res);
return res;
}
private void dfs(int[] nums, int len, int depth, boolean[] used, Deque<Integer> path, List<List<Integer>> res) {
if (depth == len) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < len; ++i) {
if (used[i]) {
continue;
}
// 剪枝条件：i > 0 是为了保证 nums[i - 1] 有意义
// 写 !used[i - 1] 是因为 nums[i - 1] 在深度优先遍历的过程中刚刚被撤销选择，被撤销选择为false
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
continue;
}
path.addLast(nums[i]);
used[i] = true;
dfs(nums, len, depth + 1, used, path, res);
// 回溯部分的代码，和 dfs 之前的代码是对称的
used[i] = false;
path.removeLast();
}
}
}
A 1分24秒到2分00秒：讲了为什么要先排序 因为结果是要去重的，而结果都是列表形式的，那列表怎么判重呢？就是排序之后一个一个的比较，所以那还不如先排序之后再计算，在计算的过程中判断是否有重复，免得对每个结果再做一次排序去重操作。再一个，排序之后相同的元素一定重复吗？不一定，不同结果经过排序之后也可能相同
B 为什么" nums[i-1] 的used状态是被选择的，那么说明当前的nums[i] 是 nums[i-1]的下一层路径。"
原因：因为往下层递归的话，一直再往下层走，dfs还未return，也就是说used还没有被回溯为未选择状态，所以同一条分支上，nums[i-1] 的used状态一定是被选择的。
为什么“ 如果 nums[i-1] 的状态是没被选择的，那么说明当前 的nums[i] 是nums[i-1] 同层路径。”
原因：递归到叶节点，开始往上回溯了，回溯到某一层时把used[i-1]回溯为未选择状态，然后for循环i++横向移动，自然这时再判断used[i-1]就一定是未选择状态。
