| java数据结构与算法刷题目录（剑指Offer、LeetCode、ACM）-----主目录-----持续更新(进不去说明我没写完)：https://blog.csdn.net/grd_java/article/details/123063846 |
|---|
文章目录
| 解题思路 |
|---|
- 此题是77题的扩展题，仅仅加了一个条件而已，就是找到的k个数，必须等于n。
- 而77题，仅仅是找到k个数即可，不需要等于n
| 🏆LeetCode77. 组合https://blog.csdn.net/grd_java/article/details/136539120 |
|---|
| 增加条件后的枝剪条件 |
|---|
- 77题本身的枝剪操作依然需要
- 如果当前组合的值已经>n了，说明没有递归的必要了，因为怎么都不可能==n了。可以进行枝剪操作
| 代码 |
|---|
class Solution {
int k,n;//用来记录k和n，以免传参太多影响代码阅读性
public List<List<Integer>> combinationSum3(int k, int n) {
this.k = k;//最多几个数一组进行组合
this.n = n;//k个数需要组成的数字是多少
List<List<Integer>> lists = new ArrayList<List<Integer>>();//用于保存答案
//使用数组来记录枚举过程中的结果，优点：速度快，击败100%用户必备。
//缺点：理解较难，且需要动态维护数组下标，实现链表的效果
Integer[] records = new Integer[k];//用于记录当前枚举（回溯枚举）的组合
backTracking(lists,records,0,1,0);//回溯算法，参数的含义看下面回溯方法的注释
return lists;
}
/**
* 回溯
* @param lists 答案需要的
* @param records 当前正在组合回溯的，也就是当前正在枚举
* @param row 代表records的下标，他表示当前是尝试枚举第几个数
* @param column 代表当前可以枚举的数的范围的左边界，必须<=9 ,因为题目规定只能使用数字1-9.例如column当前是4，则可选范围为[4,9]
* @param sum 用于记录当前records中元素的和。
*/
public void backTracking(List<List<Integer>> lists, Integer[] records,int row,int column,int sum){
//如果column>9 就没有数可以枚举了，因为只能1-9的数。sum>n也没必要继续进行当前枚举，因为我们要找的是sum == n
if(column>9 || sum>n) return;
else if(records.length + 9 - column + 1 < k) return;//剪枝操作，如果剩下可用的数字，不够组成k个数，就不继续递归
else{//否则继续递归
records[row] = column;//当前数字取column放入row位置
int curSum = sum+column;//记录取完当前数字后的和
if( curSum > n) return;//剪枝：如果这个值>n,就没必要继续枚举，因为我们只要 = n的
if(row == k-1){//如果row == k-1，说明刚好k个数，因为row是数组下标，从0开始
if(curSum == n)//找到k个数，如果这k个数刚好和为n，就找到一个正确答案
lists.add(List.of(records));
}else{//如果不够k个数，继续枚举
backTracking(lists,records,row+1,column+1,curSum);
}
//不取当前数字column放入row位置，选择从后面继续找
backTracking(lists,records,row,column+1,sum);
}
}
}
