组合总和III
题目详细:LeetCode.216
做过上一题组合后,再来写这道题就显得得心应手了,通过理解回溯算法的模版,也总结出了算法中的一些特点:
- 回溯算法与递归算法类似,同样需要参数、结束条件和主体逻辑
- 回溯算法我们可以将它看作是一棵二叉树,树丛根节点到叶子节点的一条路径,就是一个结果:
- 结束条件就相当于遇到了叶子节点,保存当前路径,返回上一层
- for循环相当于是一个选择结构,因为
每个数字最多使用一次
- 同时for循环的次数也决定了树的宽度
- 递归的次数就相当于是for循环的嵌套次数,决定了树的深度
- 每一次递归结束后,都要对结果进行回溯,相当于从叶子节点退回上一个节点,然后继续循环,进入下一条路径,寻找另一个结果
- 从上述回溯过程,我们也可以发现,回溯法类似对树进行深度优先遍历,找出所有的路径,保存符合预期结果的路径,所以本质上也是一种暴力法。
Java解法(回溯,递归):
class Solution {List<List<Integer>> ans = new ArrayList<>();Deque<Integer> path = new ArrayDeque<>();public void backtracking(int k, int n, int sum, int startNum){// 结束条件,叶子节点if(path.size() == k && sum == n){this.ans.add(new ArrayList<>(path));return;}// for循环,选择节点for(int i = startNum; i <= 9; i++){this.path.offer(i);sum += i;// 递归,深度优先遍历backtracking(k, n, sum, i + 1);// 回溯,返回叶子节点的上一节点this.path.removeLast();sum -= i;// 继续循环,进入其他节点,寻找符合结果的路径}}public List<List<Integer>> combinationSum3(int k, int n) {this.backtracking(k, n, 0, 1);return this.ans;}
}
电话号码的字母组合
题目详细:LeetCode.17
这道题我一开始的思路和前两道练习搞混了,琢磨了一个钟之后,看了题解才恍然大悟,原来这道题的不同点是在于在不同集合中找组合。
详细的解释可以看题解:《代码随想录—电话号码的字母组合》
Java解法(递归, 回溯):
class Solution {public List<String> ans = new ArrayList<>();public StringBuffer path = new StringBuffer();public char[][] mapper_all = {{'a','b','c'},{'d','e','f'}, {'g','h','i'}, {'j','k','l'}, {'m','n','o'}, {'p','q','r','s'}, {'t','u','v'}, {'w','x','y','z'}};public List<String> letterCombinations(String digits) {this.backtracking(digits, 0);return this.ans;}public void backtracking(String digits, int startNum){if(path.length() == digits.length()){if(path.length() != 0){ans.add(path.toString());}return;}char[] mapper = mapper_all[digits.charAt(startNum) - '0' - 2];for(int i = 0; i < mapper.length; i++){this.path.append(mapper[i]);// 递归,注意startNum + 1,表示要处理下一个数字了backtracking(digits, startNum + 1);this.path.deleteCharAt(path.length() - 1);}}
}
注意这里for循环,可不像前两天的练习(LeetCode.77和.216)中从startIndex开始遍历的。
因为本题每一个数字代表的是不同集合,也就是求不同集合之间的组合,而之前的练习(LeetCode.77和.216)是求同一个集合中的组合!