力扣17.電話號碼的字母組合
鏈接: link
思路
這道題容易想到用嵌套的for循環實現，但是如果輸入的數字變多，嵌套的for循環也會變長，所以暴力破解的方法不合適。
可以定義一個map將數字和字母對應，這樣就可以獲得數字字母的映射了，遞歸中index參數理解成遍歷過的第幾個數字，也可以想成二叉樹的深度，當index值等于digits長度時表示已經遞歸到葉子節點，要結束遞歸了。
關于把回溯問題想成二叉樹的思路，可以參照之前寫的回溯1的思路
class Solution {List<String> res = new ArrayList<>();// 保存最后結果public List<String> letterCombinations(String digits) {if(digits == null || digits.length() == 0){return res;}//初始對應所有的數字，為了直接對應2-9，新增了兩個無效的字符串""String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};backTrace(digits,numString,0);return res;}StringBuilder sb = new StringBuilder();// 字符串拼接void backTrace(String digits, String[] numString,int index){if(index == digits.length()){res.add(sb.toString());return;}//當前 數字對應的字符串String str = numString[digits.charAt(index) - '0'];for(int i = 0;i<str.length();i++){sb.append(str.charAt(i));backTrace(digits,numString,index+1);sb.deleteCharAt(sb.length() - 1);}}
}
思路
這道題和回溯1出現的題有區別，但是思路相似，這道題可以出現重復的元素。所以遞歸下一層start參數不用+1
39.組合總和
鏈接: link
class Solution {List<List<Integer>> res = new ArrayList();List<Integer> path = new ArrayList();public List<List<Integer>> combinationSum(int[] candidates, int target) {backTrace(candidates,target,0,0);return res;}void backTrace(int[] candidates,int target,int sum, int start){if(sum == target){res.add(new ArrayList(path));return;}for(int i = start;i < candidates.length;i++){if (sum > target) {continue;}sum += candidates[i];path.add(candidates[i]);backTrace(candidates,target,sum,i);sum -= candidates[i];path.remove(path.size() - 1);}}
}
