1. LeetCode 216. 组合总和 III
1.1 思路
- 这题与77.组合的区别在于给我们的是一个和为n的限制，集合固定在[1,9]。
- 思路和77.组合大概相同，同样是通过回溯算法的递归帮我们控制for循环的嵌套层数，也是抽象成一个树形结构。这里的取数之后，剩下的集合就不包括前面取过的数，比如取1后剩下集合[2,9]，取2后剩下集合[3,9]，为什么没了1呢？因为我们求得是组合不是排列。我们如何控制这个集合范围呢？通过startIndex来控制。而我们的树的深度是由k来控制的，取几个元素就是递归几层。树的宽度是由最初的集合大小9来控制的。
- 定义全局变量path来收集结果，然后result放入多个path结果，因为结果可能不止一个
- 回溯函数的参数和返回值：返回值void，参数targetSum也就是n，k，sum收集路径已有的和，startIndex
- 终止条件：如果path.size()==k说明已经取够数作为组合了，因为结果在叶子节点上，那么可以判断sum是否等于targetSum，等于说明path路径符合就可以把其加入result然后返回了
- 单层搜索的逻辑：i从startIndex开始，范围为i<=9，取了数i之后就可以用sum加上。然后把数i加入到path中。然后就回溯了，把参数传入，其中的startIndex为i+1。然后是回溯的过程，要把sum减去数i，然后path弹出数i，比方说这一层已经取过12了，如何取到13呢？就是先把2弹出，再去取3，因此我们要先把数2弹出才可
1.2 代码
// class Solution { List<List<Integer>> result=new ArrayList<>(); LinkedList<Integer> path=new LinkedList<>(); public List<List<Integer>> combinationSum3(int k, int n) { backtracking(k,n,1,0); return result; } public void backtracking(int k,int n,int startIndex,int sum){ if(path.size()==k){ if(sum==n){ result.add(new ArrayList(path)); } return; } for(int i=startIndex;i<=9;i++){ path.add(i); sum+=i; backtracking(k,n,i+1,sum); path.removeLast(); sum-=i; } } }
1.3 剪枝优化思路
- 在每一层中如果此时sum已经大于targetSum就没有继续递归取数的必要了，已经不可能符合，因此可以直接return
- 然后是for循环的优化：当前递归里组合已经有path.size()个元素了，题目需要k个，就还需要k-path.size()个，那我们还需要取的元素至多可以让你从9-(k-path.size())+1个位置上开始取了，+1是为了把下标补齐。比如我们此时要取k=3个数，已经取了1个了，还剩2个，那么此时至多可以从9-(3-1)+1=8，这个位置开始取[8,9]还剩下2个元素。那么9-(k-path.size())+1这个就是作为i的范围了
1.4 代码
// class Solution { List<List<Integer>> result = new ArrayList<>(); LinkedList<Integer> path = new LinkedList<>(); public List<List<Integer>> combinationSum3(int k, int n) { backTracking(n, k, 1, 0); return result; } private void backTracking(int targetSum, int k, int startIndex, int sum) { // 减枝 if (sum > targetSum) { return; } if (path.size() == k) { if (sum == targetSum) result.add(new ArrayList<>(path)); return; } // 减枝 9 - (k - path.size()) + 1 for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) { path.add(i); sum += i; backTracking(targetSum, k, i + 1, sum); //回溯 path.removeLast(); //回溯 sum -= i; } } }
2. LeetCode 17. 电话号码的字母组合
2.1 思路
- 首先要解决的问题是题目映射的问题，我们输入的虽然是字符串，但这个字符串是一个数字，用这个数字到字符串要做个映射，我们可以用map也可以用二维数组做映射，初始化数组letterMap长度为10，下标2到9这8个位置就是对应的字符串（字符串本身也是个数组，因此是二维的）。
- 我们可以通过for循环来遍历，但由于给的数字长度是不确定的，用几个for循环就不好控制了，就可以通过回溯算法的递归来控制for循环的嵌套次数
- 因此我们可以抽象为一个树形结构，树的深度就是数字的长度，树的宽度是由每一个数字所对应的字母的长度来控制的。结果就是都在叶子节点上，也就是递归结束的地方
- 定义两个全局变量，str用来收集单个结果，result是个字符串数组，用来收集所有结果
- 回溯函数的参数和返回值：返回值void，参数就是数字字符串digits，index表示我传入的字符串遍历到哪里了。为什么这题不像上面的一样弄个startIndex呢？因为这题我们不是在同一个集合里求元素，而是多个的，因此不需要控制集合里我们遍历过哪些元素。
- 终止条件：当index==digits.length()时即这个数字字符串的最后一位的下一位，如果是最后一位的话我们还应该要进行处理的，所以是最后一位的下一位。然后就收获叶子节点的结果，result.add(str.toString())然后return。
- 单层搜索的逻辑：int digit=digits[index]-'0'，因为本身是个字符，因此减去字符0才变成一个数字，然后获取到字符串就是String letter=letterMap[digit]，然后在for循环里取字符，就正常的遍历顺序，然后要在str里存放我们取的字符，str.append(letter.charAt(i))，然后是下一层递归backtracking(digits,index+1)，然后就是回溯了，要把当前位置的元素弹出，str.deleteCharAt(str.length()-1)，因为我们要继续要右边取数遍历
- 本题不需要剪纸，因为要的就是所有可能的组合
2.2 代码
// class Solution { //设置全局列表存储最后的结果 List<String> list = new ArrayList<>(); public List<String> letterCombinations(String digits) { if (digits == null || digits.length() == 0) { return list; } //初始对应所有的数字，为了直接对应2-9，新增了两个无效的字符串"" String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; //迭代处理 backTracking(digits, numString, 0); return list; } //每次迭代获取一个字符串，所以会设计大量的字符串拼接，所以这里选择更为高效的 StringBuild StringBuilder temp = new StringBuilder(); //比如digits如果为"23",num 为0，则str表示2对应的 abc public void backTracking(String digits, String[] numString, int num) { //遍历全部一次记录一次得到的字符串 if (num == digits.length()) { list.add(temp.toString()); return; } //str 表示当前num对应的字符串 String str = numString[digits.charAt(num) - '0']; for (int i = 0; i < str.length(); i++) { temp.append(str.charAt(i)); //c backTracking(digits, numString, num + 1); //剔除末尾的继续尝试 temp.deleteCharAt(temp.length() - 1); } } }
