第一题

17. 电话号码的字母组合

题目描述：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

思路

我们可以把这道题转换成另一种更好理解的方式。想象一下，现在我们眼前有编号为“0”和“1”的两个箱子。“0”号箱子可以放入“a”，“b”，“c”三张牌，“1”号箱子可以放入“d”，“e”，“f”三张牌。问，一共有几种搭配方案？

穷举法

在这里插入图片描述
一个很简单的思路，我们可以进行两层for循环，穷举每一种可能的组合。第一层for循环遍历“0”号箱子的每一种可能，也就是从‘a’到‘c’。第二层for循环遍历“1”号箱子的每一种可能，也就是从‘d’到‘f’。

List result = new ArrayList<>();
StringBuilder path = new StringBuilder<>();for(char s1 = 'a'; s1 <= 'c'; s1++){path.append(s1);for(char s2 = 'd'; s2 <= 'f'; s2++){path.append(s2);result.add(path.toString());}
}return result;

我们现在已经知道了示例1的每一位是什么，自然可以写出上面的代码。但是，实际上digits是不确定的，我们无法知道它的具体长度和每一位，那怎么知道要如何写for循环？

回溯法

一个更好的思路，是用递归函数来代替多层for循环，每一层递归就相当于一层for循环。在递归完digits最后一个元素后，结束递归。

class Solution {private List result = new ArrayList();private StringBuilder path = new StringBuilder();private String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};/*** 返回digits能表示的字母组合* @param String digits，digits的每一位对应numString中的一个String* @return List result，digits能表示的字母组合*/public List letterCombinations(String digits) {if(digits.length() == 0 || digits == null){return result;}// 从digits[0]开始搜索，也是首次递归dfs(0, digits);return result;}/*** 递归搜索digits的每一位* @param int step，step代表digits的第几位，同时也代表了递归的第几层* @param String digits，digits的每一位对应numString中的一个字符串num*/private void dfs(int step, String digits){// 如果递归完digits最后一个元素，那么保存结果，结束递归if(step == digits.length()){result.add(path.toString());return;}// 获取digits的第step位元素char idx = digits.charAt(step);// 获取digits的第step位元素对应的字符串String num = numString[idx - '0'];// 对digits的第step位元素对应的字符串num进行“树层遍历”for(int i = 0; i < num.length(); i++){char item = num.charAt(i);// 放入第step位元素对应的字符path.append(item);// 进行“树枝遍历”，继续递归遍历第step + 1位元素对应的字符dfs(step + 1, digits);// 清空第step位元素对应的字符path.deleteCharAt(path.length() - 1);}// 如果对这一层完成了“树层遍历”，那么返回上一层return;}
}

结合示例1来看。在递归的第0层，首先遍历digits[0]，‘2’。'2’对应的num为"abc"，接下来就对num进行“树层遍历”。在第0层递归的“树层遍历”中，第一次选择将‘a’放入“0”号箱子中，然后进入下一层递归进行“树枝遍历”，选择放入“1”号箱子中的字符。同样的，在第1层递归的“树层遍历”中，第一次选择将‘d’放入“1”号箱子中，然后进入下一层递归进行“树枝遍历”。当到达第2层递归时，已经递归完digits最后一个元素，那么保存结果，结束递归。

在这里插入图片描述

现在，回到了第1层递归的“树层遍历”中。第一次我们选择将‘d’放入“1”号箱子中，现在我们要将‘d’从“1”号箱子中取出（path.deleteCharAt(path.length() - 1)），选择将‘e’放入“1”号箱子中。

当我们把“def”都选择过一遍之后，返回第0层递归的“树层遍历”中。第一次我们选择将‘a’放入“0”号箱子中，现在我们要将‘a’从“0”号箱子中取出（path.deleteCharAt(path.length() - 1)），选择将‘b’放入“0”号箱子中。

回溯法通过递归函数，可以实现多次for循环，遍历所有可能的结果。

总结

最后，我们可以总结出回溯法使用递归函数实现多层循环的代码模版。

void dfs(){if(达到了递归条件){保存结果返回}for(进行“树层循环”){添加元素dfs(进行“树枝循环”)移除元素}
}

第二题

46. 全排列

题目描述：给定一个不含重复数字的数组nums，返回其所有可能的全排列。你可以按任意顺序返回答案。

示例1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

思路

这道题可以和第一题一样，转换成往箱子里放牌。想象一下，数组nums的长度为3，我们就是要遍历编号为“0”，“1”，“2”的三个箱子。“0”号箱子可以放入“1”，“2”，“3”三张牌，“1”号箱子也可以放入“1”，“2”，“3”三张牌。但是，和第一题不一样的地方在于，这道题里用过的牌不可以再用。当“0”号箱子可以放入“1”时，“1”号箱子就不可以放入“1”了，只能放“2”或“3”两张牌。同理，当“0”号箱子可以放入“2”时，“1”号箱子就不可以放入“2”了，只能放“1”或“3”两张牌。

回溯法

同样的，我们使用递归函数来遍历数组nums的长度，进行“树枝循环”。为了实现用过的牌不可以再用，我们需要一个used数组记录哪些牌已经被用过了。

class Solution {private List> result = new ArrayList<>();private List path = new LinkedList<>();/*** 返回nums所有可能的全排列* @param int[] nums，nums的每一位是一个数字* @return List> result，nums所有可能的全排列*/public List> permute(int[] nums) {// used数组表示nums对应位置的数字是否已经被使用，默认为falseboolean[] used = new boolean[nums.length];dfs(0, nums, used);return result;}/*** 递归搜索nums的每一位* @param int step，step代表第几个箱子，同时也代表了递归的第几层* @param int[] nums，nums的每一位是一个数字* @param boolean[] used，表示nums对应位置的数字是否已经被使用*/private void dfs(int step, int[] nums, boolean[] used){// 如果递归完nums最后一个元素，那么保存结果，结束递归if(step == nums.length){result.add(new ArrayList<>(path));return;}// 第step个箱子对nums的元素进行“树层遍历”for(int i = 0; i < nums.length; i++){// 如果该元素没有放入step之前的箱子里，那么就可以放入第step个箱子if(!used[i]){// 将nums的元素放入第step个箱子path.add(nums[i]);// 记录该元素已经被使用过used[i] = true;// 进行“树枝遍历”，继续递归遍历第step + 1个箱子dfs(step + 1, nums, used);// 将第step个箱子的元素取出path.remove(path.size() - 1);// 记录该元素没有被使用过used[i] = false;}}return;}
}

在这里，nums数组的长度就是箱子的个数。在第0个箱子，对nums的元素进行“树层遍历”，可以放入“1”，“2”，“3”三张牌。第一次选择将‘1’放入“0”号箱子中，然后进入下一层递归进行“树枝遍历”，选择放入“1”号箱子中的数字。同样的，在第1层递归的“树层遍历”中，此时“1”已经被用过了，可以选择的数字只有“2”和“3”。第一次选择将‘2’放入“1”号箱子中，然后进入下一层递归进行“树枝遍历”。当到达第2层递归时，只剩下“3”可以用，放入“2”号箱子中，进行下一层递归。在第3层递归中，已经遍历完nums数组的长度，保存答案并返回。
在这里插入图片描述
现在，回到了第2层递归的“树层遍历”中。因为第0层循环用了‘1’，第1层循环用了‘2’，所以第2层循环只有‘3’可以用。现在结束第2层循环，回到第1层循环。