当前位置：首页 > news >正文

代码随想录算法训练营第24天25天|● 77. 组合● 216.组合总和III ● 17.电话号码的字母组合

news 2025/6/28 4:01:50

77组合

看完题后的思路

在这里插入图片描述

void f（数组，startIndex）
递归终止
if（startIndex数组长度||path.sizek）{
if(path.size==k){
加入}
}
递归

for（；startIndex<num.size；startIndex++）{
加入；
4.剪枝
if（path.size>k）{
吐出来；
return；
}
f（num，startIndex+1）；
// 回溯
吐出来

}

代码

 List<List<Integer>> ires = new ArrayList<>();ArrayList<Integer> ipath = new ArrayList<>();public List<List<Integer>> combine(int n, int k) {combineTB(n,0,k);return ires;}public void combineTB(int n,int startIndex,int k){//终止if (startIndex==n||ipath.size()==k){if (ipath.size()==k){ires.add(new ArrayList<>(ipath));}return;}for (; startIndex<n; startIndex++) {// 尝试加入ipath.add(startIndex);// 剪枝if (ipath.size()>k){  // 这一步永远不会生效，因为终止条件已经剪枝了return;}// 进入下一层combineTB(n,startIndex+1,k);// 回溯ipath.remove(ipath.size()-1);// 进入本层下一个 ----->}}

复杂度

优化：添加剪枝条件

      // 剪枝if (ipath.size()==k||n-startIndex+1<(k-ipath.size())){return;}

后一个剪枝条件表示当前可加入的元素<所缺的元素

在这里插入图片描述

List<List<Integer>> ires = new ArrayList<>();ArrayList<Integer> ipath = new ArrayList<>();public List<List<Integer>> combine(int n, int k) {combineTB(n,1,k);return ires;}public void combineTB(int n,int startIndex,int k){//终止if (startIndex>n||ipath.size()==k){if (ipath.size()==k){ires.add(new ArrayList<>(ipath));}return;}for (; startIndex<=n; startIndex++) {// 剪枝if (ipath.size()==k||n-startIndex+1<(k-ipath.size())){return;}// 尝试加入ipath.add(startIndex);// 剪枝// if (ipath.size()>k){//     return;// }// 进入下一层combineTB(n,startIndex+1,k);// 回溯ipath.remove(ipath.size()-1);// 进入本层下一个 ----->}}

递归深度： k
递归宽度：n-startIndex+1<(k-ipath.size())
在这里插入图片描述

收获

三刷看一遍
组合问题模板
做回溯题步骤
（0）判断问题类型
（1）树状图
（2）递归三部曲
（3）剪枝条件

216.组合总和III

看完题后的思路

a+b=b+a，这是一个组合问题
在这里插入图片描述

void f（n，k，startIndex，sum） // 纵向剪枝
终止条件
if（path.size==k）{
if(和为n){
加入
}
return；
}
回溯模型
剪枝条件
if（path内的数+当前树大于k） return

代码

  List<List<Integer>> ires = new ArrayList<>();ArrayList<Integer> ipath = new ArrayList<>();//216. 组合总和 IIIpublic List<List<Integer>> combinationSum3(int k, int n) {combinationSum3BT(k,n,0,1);return ires;}public void combinationSum3BT(int k, int n,int sum,int startIndex ) {if(ipath.size()==k){// 终止+纵向剪枝if (sum==n){ires.add(new ArrayList<>(ipath));}return;}for (; startIndex <=9 ; startIndex++) {// 纵向剪枝if (startIndex+sum>n){return;  // (纵)横向剪枝  因为兄弟节点 (startIndex++)+sum也一定>k}sum+=startIndex;ipath.add(startIndex);combinationSum3BT(k,n,sum,startIndex+1);// 回溯sum-=startIndex;ipath.remove(ipath.size()-1);// 本层下一个}}

复杂度

最坏时间复杂度 0(9*k)
在这里插入图片描述

收获

1.本题让组合剪枝变得明朗,三刷大脑过一遍
2, 组合问题中的纵横剪枝
==有图==

17.电话号码的字母组合

看完题后的思路

在这里插入图片描述

本体可以抽象为若干个筐，筐中有若干个球，每次从筐中取一个球，所有可能的球的组合。
本质上是只取组合传统递归树最左边分支
void f（map<数字，字母>，startIndex，[数字]）
if（ipath.size==数字个数）{
加入结果；
return；
}
回溯算法
num【startIndex】；
取出对应的字母；
for（字母）{
加入ipath；
f（map<数字，字母>，startIndex+1，[数字]）
回溯；
}

代码

 StringBuilder sbPath = new StringBuilder();ArrayList<String> slistRes = new ArrayList<>();public List<String> letterCombinations(String digits) {if (digits==null||digits.length()==0){return slistRes;}String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};letterCombinationsBT(digits,numString,0);return slistRes;}public void letterCombinationsBT(String digits,String[] map,int startIndex) {// 出口if (sbPath.length()==digits.length()){slistRes.add(new String(sbPath));return;}// 回溯算法char c = digits.charAt(startIndex);String s = map[c - '0'];// 对应的字符组合// 内部回溯for (char c1 : s.toCharArray()) {sbPath.append(c1);// 下一层递归letterCombinationsBT(digits,map,startIndex+1); // 关键是startIndex+1// 回溯sbPath.delete(sbPath.length()-1,sbPath.length());// 进入本层下一层}}