216.组合总和III
题目链接：力扣
思路
这道题目和77.组合是一类题目，如果不采用剪枝操作，就可以按照模板方法进行
使用叠加for循环的方法是没有办法涵盖所有情况的，没有办法直接控制for循环的层数，所以还是需要使用回溯算法
组合总和|||
根据77.组合仿写
class Solution { List<Integer> nums = new ArrayList<>(); List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> combinationSum3(int k, int n) { traversal(k,n,1); return result; } void traversal(int k, int n, int startIndex) { if ( nums.size() == k ) { // 检测结果是否满足 int sum = 0; for (int num : nums) { sum += num; } if (sum == n) { result.add(new ArrayList(nums)); } return; } for (int i = startIndex; i <= 9; i++) { nums.add(i); traversal(k,n,i+1); nums.remove(nums.size() - 1); } } }
进行剪枝操作之后
class Solution { List<Integer> nums = new ArrayList<>(); List<List<Integer>> result = new ArrayList<>(); int sum = 0; public List<List<Integer>> combinationSum3(int k, int n) { backtracking(k,n,1); return result; } void backtracking (int k, int n, int startIndex) { if (sum > n) { return; } if (nums.size() == k) { if (sum == n) { result.add(new ArrayList(nums)); } return; } for (int i = startIndex; i <= 9 - (k - nums.size()) + 1; i++) { nums.add(i); sum += i; backtracking(k,n,i + 1); sum -= nums.get(nums.size() - 1); nums.remove(nums.size() - 1); } } }
17.电话号码的字母组合
题目链接：力扣
思路
这道题目的原理其实和组合的原理是一样的，都是可以抽象成树形结构的，只不过就是在数据类型的转换之间比较麻烦
首先需要对数字和所代表的数字之间进行映射，可以使用map集合，也可以使用二维数组。这里因为有数字对应，所以使用二维数组比较方便
String[] mappings = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
具体的流程，先从digits中获取字符数字，转换成数组的下标，获取到对应的字母字符串，进行递归组合，再进行回溯
电话号码的字母组合
class Solution { List<String> result = new ArrayList<>(); // 数字与字母集合的映射 String[] mappings = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; public List<String> letterCombinations(String digits) { if (digits == null || digits.length() == 0) { return result; } backstracking(digits, new StringBuilder(),0); return result; } // digits 原字符串 // sb 用来拼接字符串的 // index 原字符串遍历到什么位置了，当前递归遍历到哪个数字了 void backstracking (String digits,StringBuilder sb,int index) { // 终止条件 if (sb.length() == digits.length()) { result.add(new String(sb)); return; } // 先获取当前递归的数字对应的字母字符串 // 首先获取digits中的数字对应的字符串的下标 // Integer num = Integer.valueOf(String.valueOf(digits.charAt(index))); // 直接获取对应字符串的方法 String str = mappings[digits.charAt(index) - '0']; for (int i = 0; i < str.length(); i++) { sb.append(str.charAt(i)); backstracking(digits,sb,index+1); sb.deleteCharAt(index); } } }
小总结
77.组合 和 216.组合总和||| 都是属于在一个集合中组合
17.电话号码的字母组合 是在多个集合中进行组合
