java数据结构与算法刷题-----LeetCode216. 组合总和 III

java数据结构与算法刷题目录（剑指Offer、LeetCode、ACM）-----主目录-----持续更新(进不去说明我没写完)：https://blog.csdn.net/grd_java/article/details/123063846

解题思路

1. 此题是77题的扩展题，仅仅加了一个条件而已，就是找到的k个数，必须等于n。
2. 而77题，仅仅是找到k个数即可，不需要等于n

🏆LeetCode77. 组合https://blog.csdn.net/grd_java/article/details/136539120

增加条件后的枝剪条件

1. 77题本身的枝剪操作依然需要
2. 如果当前组合的值已经>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 == nif(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);}}
}