77. 組合 - 力扣（LeetCode）

class Solution {List<Integer> path = new ArrayList<>();List<List<Integer>> result = new ArrayList<>();public void backTracking(int n,int k,int startIndex){if(path.size() == k){result.add(new ArrayList(path));return;}for(int i = startIndex;i <= n;i++){//剪枝：i <= n - (k - path.size()) + 1path.add(i);backTracking(n,k,i+1);path.remove(path.size()-1);}}public List<List<Integer>> combine(int n, int k) {backTracking(n,k,1);return result;}
}

題目鏈接/文章講解：代碼隨想錄

視頻講解：帶你學透回溯算法-組合問題（對應力扣題目：77.組合）| 回溯法精講！_嗶哩嗶哩_bilibili

剪枝操作：帶你學透回溯算法-組合問題的剪枝操作（對應力扣題目：77.組合）| 回溯法精講！_嗶哩嗶哩_bilibili

216.組合總和III

題目鏈接/文章講解：代碼隨想錄

視頻講解：和組合問題有啥區別？回溯算法如何剪枝？| LeetCode：216.組合總和III_嗶哩嗶哩_bilibili

class Solution {int sum = 0;List<Integer> path = new ArrayList<>();List<List<Integer>> result = new ArrayList<>();public void backTracking(int k ,int n,int startIndex){if(path.size() == k){if(sum == n)result.add(new ArrayList(path));return;}for(int i = startIndex;i <= 9 - (k - path.size())+1;i++){path.add(i);sum += i;backTracking(k,n,i+1);path.remove(path.size()-1);sum -= i;}}public List<List<Integer>> combinationSum3(int k, int n) {backTracking(k,n,1);return result;}
}

17.電話號碼的字母組合

題目鏈接/文章講解：代碼隨想錄

視頻講解：還得用回溯算法！| LeetCode：17.電話號碼的字母組合_嗶哩嗶哩_bilibili

class Solution {StringBuilder path = new StringBuilder();List<String> res = new ArrayList<>();public void backTracking(String digits,String[] numString,int index){if(index == digits.length()){res.add(path.toString());return;}String str = numString[digits.charAt(index) - '0'];//找到數字映射的字母for(int i = 0;i < str.length();i++){path.append(str.charAt(i));//遍歷各個字母backTracking(digits,numString,index + 1);//對下個數字進行相同的步驟path.deleteCharAt(path.length()-1);//回溯}}public List<String> letterCombinations(String digits) {if(digits == null || digits.length() == 0)return res;String[] numString = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};//數字和字母的關系backTracking(digits,numString,0);return res;}
}