代码随想录刷题训练营day25：LeetCode(216)组合总和III、LeetCode(17)电话号码的字母组合

代码随想录刷题训练营day25：LeetCode(40)组合总和 II、LeetCode(216)组合总和III、LeetCode(17)电话号码的字母组合

LeetCode(40)组合总和 II
题目
在这里插入图片描述

代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;class Solution {public List<List<Integer>> result=new ArrayList<>();public List<Integer> path=new ArrayList<>();public List<List<Integer>> combinationSum2(int[] candidates, int target) {//题目含义：每个元素仅使用一次，并完成去重，产生重复的结果，进行去除//1，数组排序Arrays.sort(candidates);//2、创建状态数组，用于区别树枝重复和树层重复，树枝重复是可取的，树层重复是不可取的int[] used=new int[candidates.length];//3、调用递归函数----获取结果int startIndex=0;int sum=0;backtracking(candidates,used,target,startIndex,sum);return result;}//回溯函数public void backtracking(int[] candidates,int[] used,int target,int startIndex,int sum){if(sum>=target){if(sum==target){List<Integer> tempPath=Arrays.asList(new Integer[path.size()]);Collections.copy(tempPath, path);result.add(tempPath);}return;//退回去}for(int i=startIndex;i<candidates.length;i++){//去重的关键操作if(i>0&&candidates[i]==candidates[i-1]&&used[i-1]==0){//树枝上可以重复，树层上不可以重复-----定义一个状态变量continue;//当前回合循环不用}path.add(candidates[i]);sum=sum+candidates[i];used[i]=1;backtracking(candidates, used, target, i+1, sum);path.remove(path.size()-1);sum=sum-candidates[i];used[i]=0;//回溯，弹出来}}
}

LeetCode(216)组合总和III
题目
在这里插入图片描述

代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.ArrayBlockingQueue;class Solution {public List<Integer> path=new ArrayList<>();//存储路径public List<List<Integer>> result=new ArrayList<>();//存放结果public List<List<Integer>> combinationSum3(int k, int n) {int startIndex=1;//调用递归函数backtracking(k,n,startIndex);return result;}//设计递归函数public void backtracking(int k,int n,int startIndex){//终止条件if(path.size()==k){int sum = path.stream().reduce(Integer::sum).orElse(0);//求和数据流if(sum==n){List<Integer> pathDate=Arrays.asList(new Integer[path.size()]);Collections.copy(pathDate, path);result.add(pathDate);return;}}//进入单次递归循环for(int i=startIndex;i<=9;i++){path.add(i);backtracking(k, n, i+1);path.remove(path.size()-1);//回溯}}
}

LeetCode(17)电话号码的字母组合
题目
在这里插入图片描述

代码

import java.util.ArrayList;
import java.util.List;class Solution {public List<String> result=new ArrayList<>();//定义一个存放路径的数组----该数组可以进行操作public StringBuffer path=new StringBuffer();//存储整个数据的数组String[] date={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};public List<String> letterCombinations(String digits) {int pathlenght=digits.length();if(pathlenght==0){return result;//此时直接为空，不需要进行递归}int index=0;//调用回溯函数----得到返回值backtracking(digits,index);//是只到第几个数组；return result;}public void backtracking(String digits,int index){//判断终止条件if(path.length()==digits.length()){String pathdate=path.toString();result.add(pathdate);return;}//进入单层递归循环char c=digits.charAt(index);//转charint i=c-'0';//转intString dateString=date[i];for (int j = 0; j < dateString.length(); j++) {//执行结束也是一次循环结束String pathtemp=String.valueOf(dateString.charAt(j));path.append(pathtemp);//递归backtracking(digits, index+1);//回溯path.deleteCharAt(path.length()-1);    }}
}