本文主要是介绍力扣爆刷第123天之回溯五连刷,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
力扣爆刷第123天之回溯五连刷
文章目录
- 力扣爆刷第123天之回溯五连刷
- 一、77. 组合
- 二、216. 组合总和 III
- 三、17. 电话号码的字母组合
- 四、39. 组合总和
- 五、40. 组合总和 II
一、77. 组合
题目链接:https://leetcode.cn/problems/combinations/description/
思路:元素无重,不可复用,求组合数,可以早停。常规做法套模板。
class Solution {List<List<Integer>> resList = new ArrayList<>();List<Integer> list = new ArrayList<>();public List<List<Integer>> combine(int n, int k) {backTracking(n, k, 1);return resList;}void backTracking(int n, int k, int start) {if(list.size() == k) {resList.add(new ArrayList(list));return;}for(int i = start; i <= n && n - (k - list.size()) + 1 >= i; i++) {list.add(i);backTracking(n, k, i+1);list.remove(list.size()-1);}}
}
二、216. 组合总和 III
题目链接:https://leetcode.cn/problems/combination-sum-iii/description/
思路:元素无重,不可复选,要求和为n的k个数的组合,只需要简单的判断和早停,其他套模板。
class Solution {List<List<Integer>> resList = new ArrayList<>();List<Integer> list = new ArrayList<>();int sum = 0;public List<List<Integer>> combinationSum3(int k, int n) {if(k > n) return resList;backTracking(k, n, 1);return resList;}void backTracking(int k, int n, int start) {if(sum == n && list.size() == k) {resList.add(new ArrayList(list));return;}for(int i = start; i <= 9 && sum + i <= n; i++) {list.add(i);sum += i;backTracking(k, n, i+1);sum -= i;list.remove(list.size()-1);}}}
三、17. 电话号码的字母组合
题目链接:https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
思路:集合无重,元素不可复用,本题不同的点是所使用的集合是可以变化的,每次向下递归需要更换下一个集合。
class Solution {List<String> list = new ArrayList<>();StringBuilder builder = new StringBuilder();String[] source = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};public List<String> letterCombinations(String digits) {if(digits.equals("")) return list;backTracking(0, digits);return list;}void backTracking(int start, String digits) {if(builder.length() == digits.length()) {list.add(builder.toString());return;}String temp = source[digits.charAt(start) - '0'];for(int i = 0; i < temp.length(); i++) {builder.append(temp.charAt(i));backTracking(start+1, digits);builder.deleteCharAt(builder.length()-1);}}
}
四、39. 组合总和
题目链接:https://leetcode.cn/problems/combination-sum/description/
思路:集合无重,元素可复选,求和为K的组合数,向下递归索引位置为i不用加1,确保单个元素可以复选,排序后可以早停。其他套模板。
class Solution {List<List<Integer>> resList = new ArrayList<>();List<Integer> list = new ArrayList<>();int sum = 0;public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates);backTracking(candidates, target, 0);return resList;}void backTracking(int[] candidates, int target, int start) {if(sum == target) {resList.add(new ArrayList(list));return;}for(int i = start; i < candidates.length && sum + candidates[i] <= target; i++) {sum += candidates[i];list.add(candidates[i]);backTracking(candidates, target, i);sum -= candidates[i];list.remove(list.size()-1);}}}
五、40. 组合总和 II
题目链接:https://leetcode.cn/problems/combination-sum-ii/description/
思路:集合元素有重,不可复选,求和为K的组合数,数组和排序,排序后,纵向不去重,横向去重,横向只需要大于初始索引,前后两个值想对,即去重。其他一样。
class Solution {List<List<Integer>> resList = new ArrayList<>();List<Integer> list = new ArrayList<>();int sum = 0;public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);backTracking(candidates, target, 0);return resList;}void backTracking(int[] candidates, int target, int start) {if(sum == target) {resList.add(new ArrayList(list));return;}for(int i = start; i < candidates.length && sum + candidates[i] <= target; i++) {if(i > start && candidates[i] == candidates[i-1]) continue;sum += candidates[i];list.add(candidates[i]);backTracking(candidates, target, i+1);sum -= candidates[i];list.remove(list.size()-1);}}}
这篇关于力扣爆刷第123天之回溯五连刷的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!