组合型回溯模板题

灵神算法
文章有的可能是格式问题，可以从这里看原文https://www.yuque.com/pkqzyh/nfi24z/gqc6wxxbkc67sinh#h1fq0

回溯算法大家刚学的时候可以去b站听灵神的算法基础课

77. 组合(n 个数选 k 个数)

题目描述

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

解题思路

组合问题，相对于排列问题而言，不计较一个组合内元素的顺序性（即 [1, 2, 3] 与 [1, 3, 2] 认为是同一个组合），因此很多时候需要按某种顺序展开搜索，这样才能做到不重不漏。

如果组合里有 1 ，那么需要在 [2, 3, 4] 里再找 1 个数；

如果组合里有 2 ，那么需要在 [3, 4] 里再找 1数。注意：这里不能再考虑 1，因为包含 1 的组合，在第 1 种情况中已经包含。

依次类推（后面部分省略），以上描述体现的递归结构是：在以 n 结尾的候选数组里，选出若干个元素。

path这个数组的大小如果达到k，说明我们找到了一个子集大小为k的组合了，在图中path存的就是根节点到叶子节点的路径。

:::color3
如果for循环选择的起始位置之后的元素个数已经不足我们需要的元素个数了，那么就没有必要搜索了

已经选择的元素个数：path.size();
还需要的元素个数为: k - path.size();
在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历

为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。

举个例子，n = 4，k = 3，目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。

:::

class Solution {private List<List<Integer>> res = new ArrayList<>();private List<Integer> path = new ArrayList<>();public List<List<Integer>> combine(int n, int k) {if (n<k) return  res;dfs(1,n,k);return res;}/**** @param x 表示当前填写的是第几个位置* @param n n表示有几个整数* @param k k表示组合要有几个数*/void dfs(int x,int n,int k){if(path.size()==k){res.add(new ArrayList<>(path));return;}for(int i=x;i<=n-(k-path.size())+1;i++){path.add(i);dfs(i+1,n,k);path.remove(path.size()-1);}}
}

1. 变量说明

res：用于存储所有有效的组合，类型为List<List<Integer>>。
path：用于存储当前正在生成的组合，类型为List<Integer>。

2. 方法说明

combine(int n, int k)：
- 这是主方法，用于初始化并调用递归方法dfs。
- 如果n < k，直接返回空结果（因为无法生成组合）。
- 否则，调用dfs(1, n, k)开始生成组合。
dfs(int x, int n, int k)：
- 这是递归方法，用于生成组合。
- x：表示当前处理的起始位置（从x开始选择数）。
- n：表示整数的范围（从1到n）。
- k：表示组合的长度（需要选择k个数）。

3. 递归逻辑

终止条件：
- 如果path.size() == k，说明当前组合已经生成完毕，将其加入结果列表res中。
- 注意：res.add(new ArrayList<>(path))是为了避免引用传递问题，确保每次添加的是一个新的列表。
递归过程：
- 使用一个循环从x开始遍历到n - (k - path.size()) + 1。
 - 这里的n - (k - path.size()) + 1是一个剪枝条件，确保剩余的数足够填充组合的剩余位置。
- 在循环中：
 - 将当前数i加入path。
 - 递归调用dfs(i + 1, n, k)，处理下一个位置。
 - 递归返回后，移除path中的最后一个数（回溯），以便尝试其他可能的组合。

216. 组合总和 III

题目描述

解题思路

对于数字 1-9，每个数字可以选择也可以不选择

终止条件：
- 如果n < 0，说明当前组合的和已经超过了目标值，直接返回。
- 如果path.size() == k且n == 0，说明当前组合已经生成完毕且和等于目标值，将其加入结果列表res中。
递归过程：
- 使用一个循环从x开始遍历到9 - (k - path.size()) + 1。
 - 这里的9 - (k - path.size()) + 1是一个剪枝条件，确保剩余的数足够填充组合的剩余位置。
- 在循环中：
 - 将当前数i加入path，并更新剩余和n -= i。
 - 递归调用dfs(i + 1, n, k)，处理下一个位置。
 - 递归返回后，移除path中的最后一个数（回溯），并恢复剩余和n += i，以便尝试其他可能的组合。

class Solution {private List<List<Integer>> res = new ArrayList<>();private List<Integer> path = new ArrayList<>();public List<List<Integer>> combinationSum3(int k, int n) {dfs(1,n,k);return  res;}/**** @param x 表示从哪个数开始枚举* @param n 表示剩余需要达到的和为多少* @param k 表示选了几个数*/void  dfs(int x,int n,int k){if (n<0) return;if (path.size()==k && n==0){res.add(new ArrayList<>(path));return;}for(int i=x;i<=9 - (k - path.size()) + 1;i++){path.add(i);n-= i;dfs(i+1,n,k);//恢复现场path.remove(path.size()-1);n+=i;}}
}

22. 括号生成

题目描述

解题思路

枚举填左括号还是右括号

path：用于存储当前生成的括号组合。
res：用于存储所有有效的括号组合。
cnt：用于记录当前已经使用的左括号的数量。

递归逻辑：

如果当前处理的位置x等于2*n，说明已经生成了一个完整的括号组合，将其加入结果列表res中。
如果当前左括号的数量cnt小于n，可以选择添加一个左括号，并递归处理下一个位置。
如果当前右括号的数量x - cnt小于左括号的数量cnt，可以选择添加一个右括号，并递归处理下一个位置。

class Solution {private StringBuilder path=new StringBuilder();private List<String> res=new ArrayList<>();int cnt=0;//记录左括号的个数public List<String> generateParenthesis(int n) {dfs(0,n);return res;}/**** @param x 代表当前括号所在的位置* @param n 代表要生成多少对括号*/void dfs(int x,int n){if (x==2*n){res.add(path.toString());}//当前位置可以选左括号或者右括号，如果左括号个数已经到达n，就不能选左括号了//如果右括号的个数小于n就可以选中右括号//注意:左括号的个数不能小于右括号if (cnt<n){path.append('(');cnt++;dfs(x+1,n);path.deleteCharAt(path.length()-1);cnt--;}//选右括号if(x-cnt<cnt){path.append(')');dfs(x+1,n);path.deleteCharAt(path.length()-1);}}
}