17. 电话号码的字母组合
还是不会这种排列组合问题，需要多加练习
其中涉及字符串的拼接时需要用StringBuffer拼接，并且判断字符串为空时不要判断str==""；这无法判断，
1.用s.length==0 来判断空
2.用字符串函数s.equals("")这种方法判断为空。
力扣非常好的题解
public static List<String> letterCombinations(String digits) {
if(digits.length==0) return new ArrayList<>();
Map<String,String> map=new HashMap<>();
String[] nums={"2","3","4","5","6","7","8","9"};
String[] values={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
for(int i=0;i<nums.length;i++){
map.put(nums[i],values[i]);
} //test is ok
List<String> res=new LinkedList<>();
backtrack(new StringBuilder(),digits,res,0,map);
return res;
}
//关键是这部分的递归代码，所有的组合代码都是这种套路
public static void backtrack(StringBuilder combination, String nextdigit,List<String> res,int i,Map<String,String> map){
//第一个是参数时用于拼接字符的参数，第二个是“23”这种字符串，res是最后的结果，i表示递归第几个字符，map是保存的键值对
if(i==nextdigit.length()){
res.add(combination.toString());
return;
}
else{
//取出每一个字符
String s=String.valueOf(nextdigit.charAt(i));
String letters=map.get(s);
for(int j=0;j<letters.length();j++){ //这一步就像走迷宫的四个方向一样，对每一种可能进行递归
String letter=String.valueOf(letters.charAt(j));
backtrack(new StringBuilder(combination+letter),nextdigit,res,i+1,map);
}
}
}
46. 全排列
这是一类题目都是递归+回溯
class Solution {
//整个过程设计的两个知识点
List<List<Integer>> res=new ArrayList<>();
List<Integer> temp=new ArrayList<>();
boolean []visited=new boolean[100]; //暂定100
public List<List<Integer>> permute(int[] nums) {
Process(nums,0);
return res;
}
public void Process(int []nums,int i){
if(i==nums.length)
{
//这一步不知道语法，可以这样对list进行拷贝的，并且不损耗原来的temp数组便于之后的递归
res.add(new ArrayList<>(temp));
return;
}
for(int j=0;j<nums.length;j++) {
if (!visited[j]) {
visited[j] = true;
temp.add(nums[j]);
Process(nums, i+ 1);
//回溯，要将节点的访问标记复原，并且需要将list列表给复原（即移除数据），即和原来的操作相反的操作就是回溯
visited[j] = false;
temp.remove(temp.size()-1); //将最后的元素移除,这一步没写
}
}
}
}
首先这种题也是dfs搜索问题，但是对于这种问题有个回溯的过程在这里，我就是卡在这个回溯的流程这里没搞明白，第一就是保存全排列的序列，这一步直接保存会影响后面的移除
res.add(temp);
temp=new ArrayList<>(); //本意是将temp暂存一个全排列序列，清空后再对其他序列进行全排列
return;
但是这里回溯时的本意是在原来的temp基础上从后往前来删除节点，现在直接将temp list清空这里再删除节点直接会爆越界错误的。也违背了回溯的本意。所以这里就是将temp的序列进行拷贝，
temp.remove(temp.size()-1); //将最后的元素移除
res.add(new ArrayList<>(temp)); //将原来的temp拷贝到新的空间中，并且temp不受影响，可以回溯
注意到回溯的操作和原来的操作恰好是相反的，也叫做复原状态
比如将visit从访问状态标记为未访问状态，将加入的节点从队列中取出。
总结：
1.不知道怎么将原来的list拷贝到新的空间中；
2.不知道回溯的操作是什么，我只是将状态标记了，但是没有将加入的节点取出
