每日算法Day15【组合、组合总和III、电话号码的字母组合】

77. 组合

算法链接:

77. 组合 - 力扣（LeetCode）
类型: 回溯
难度: 中等

回溯三步法：
1、确定参数返回值

2、确定终止条件

3、单层搜索逻辑

剪枝操作：
当path容量超过k时的数据可以不用遍历，故遍历边界条件判断:

for(int i = startIndex;i<= n - (k - path.size()) + 1 ; i++)

题解:

class Solution {List<List<Integer>> res = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> combine(int n, int k) {backtracking(n,k,1);return res;}void backtracking(int n,int k,int startIndex){if(path.size()==k){res.add(new ArrayList<>(path));return;}for(int i = startIndex;i<= n - (k - path.size()) + 1 ; i++){path.add(i);backtracking(n,k,i+1);path.removeLast();}}
}

216.组合总和III

算法链接:

216. 组合总和 III - 力扣（LeetCode）
类型: 回溯
难度: 中等

剪枝思路：

当路径总和大于n或者路径数大于k时，return

题解:

class Solution {List<List<Integer>> res = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();int sum = 0;public List<List<Integer>> combinationSum3(int k, int n) {getRes(k,n,1);return res;}void getRes(int k,int n,int startIdx){if (sum > n) return;if (path.size() > k) return;if (path.size()==k && sum == n){res.add(new ArrayList<>(path));return;}for(int i = startIdx;i<= 9 ; i++){path.add(i);sum+=i;getRes(k,n,i+1);sum-=i;path.removeLast();}}
}

17.电话号码的字母组合

算法链接:

17. 电话号码的字母组合 - 力扣（LeetCode）
类型: 回溯
难度: 中等

思路：将题意构建二叉树数据结构，并且使用数组存储号码值

题解:

class Solution {List<String> res = new ArrayList<>();String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};StringBuilder path = new StringBuilder();public List<String> letterCombinations(String digits) {if(digits == null || digits.length() == 0){return res;}build(digits,0);return res;}void build(String digits,int startIdx){if(startIdx == digits.length()){res.add(path.toString());return;}String str = numString[digits.charAt(startIdx)-'0'];for(int i = 0;i<str.length();i++){path.append(str.charAt(i));build(digits,startIdx+1);path.deleteCharAt(path.length()-1);}}
}