1. LeetCode 77. 組合
題目鏈接：https://leetcode.cn/problems/combinations/description/
文章鏈接：https://programmercarl.com/0077.組合.html
視頻鏈接：https://www.bilibili.com/video/BV1ti4y1L7cv
思路：利用遞歸回溯的方式。
遞歸回溯樹形圖如下：
其中，每層代表該層遞歸的處理邏輯，深度是遞歸的層數。
解法：
class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> list = new ArrayList<>();public List<List<Integer>> combine(int n, int k) {int[] input = new int[n];for (int i=0;i<n;i++) {input[i] = i+1;}int startIndex = 0;backtracking(input,k,startIndex);return res;}public void backtracking(int[] input,int k,int startIndex) {if ( k == 0) {res.add(new ArrayList(list));return;}for (int i=startIndex;i<input.length;i++) {list.add(input[i]);// 處理當前節點backtracking(input,k-1,i+1);list.removeLast(); // 撤銷當前節點}}
}
代碼解析：
單層處理完當前節點，要記得撤銷當前節點，即回溯。這樣它才能在當層排除該處理節點，并對其他節點重新進行處理，進行相同的邏輯。
2. LeetCode 216.組合總和III
題目鏈接：https://leetcode.cn/problems/combination-sum-iii/description/
文章鏈接：https://programmercarl.com/0216.組合總和III.html
視頻鏈接：https://www.bilibili.com/video/BV1wg411873x
思路：
和77一樣。只是加了求和的判斷。
解法：
class Solution {List<Integer> list = new ArrayList<>();List<List<Integer>> res = new ArrayList<>();int sum = 0;public List<List<Integer>> combinationSum3(int k, int n) {find(n,k,1);return res;}public void find(int n,int k,int startIndex) {if (list.size() == k && sum == n) {res.add(new ArrayList(list));return;}for (int i=startIndex;i<=9;i++) {// 處理節點list.add(i);sum+=i;find(n,k,i+1);// 撤銷節點list.removeLast();sum-=i;}}
}
3. LeetCode 17.電話號碼的字母組合
題目鏈接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
文章鏈接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
視頻鏈接：https://www.bilibili.com/video/BV1yV4y1V7Ug
思路：
使用回溯，但是要注意每層處理的字母集合是不同的集合，因此，每層遍歷集合時的索引都是從0開始。
解法：
class Solution {List<String> res = new ArrayList<>();String combin = "";public List<String> letterCombinations(String digits) {if (digits.length() == 0 || digits == null) {return res;}Map<Character,String> map = new HashMap<>();map.put('2',"abc");map.put('3',"def");map.put('4',"ghi");map.put('5',"jkl");map.put('6',"mno");map.put('7',"pqrs");map.put('8',"tuv");map.put('9',"wxyz");find(digits,0,map);return res;}public void find(String digits,int index,Map<Character,String> map) {// 終止條件if (index == digits.length()) {res.add(combin);return;}// 獲取當前層的字母集合，即 當前數字對應的字母集合String letters = map.get(digits.charAt(index));// 遍歷當前層的字母集合for (int i=0;i<letters.length();i++) {// 處理當前字母combin += letters.charAt(i);// 遞歸下一層find(digits,index+1,map);// 撤銷當前字母 即回溯combin = combin.substring(0,combin.length()-1);}}
}
)
