77、组合
回溯三部曲：1、确定函数头 2、确定终止条件 3、确定单层逻辑（for循环横向遍历，遍历的时候把递归当作一个黑盒）
for循环控制的是当前层的逐个元素遍历，递归层的i+1控制的是下一层从这个元素的下一个开始取，如果可以取重复元素的话，下一层依旧从i开始就可以。但是一定不能再取到i-1或更前面的元素了，因为在取i-1的时候就已经把含有i-1的所有情况（包括可以重复和不可以重复的情况）都取过了。
class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new LinkedList<>();public List<List<Integer>> combine(int n, int k) {backingTrace(n,k,1);return res;}public void backingTrace(int n, int k, int startIndex){if(path.size() == k){res.add(new ArrayList<>(path));return;}for(int i = startIndex; i <=n; i++){path.add(i);backingTrace(n, k, i + 1);path.removeLast();}}
}216、组合总和
思路和上一题差不多，注意sum如果已经大于目标值，没必要再组合下去了，我们组合出来的和都是递增的。
class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new LinkedList<>();public List<List<Integer>> combinationSum3(int k, int n) {backingTrace(k,n,1, 0);return res;}private void backingTrace(int k, int n, int startIndex,int sum){if(sum > n){return;}if(path.size() == k){if(sum == n){res.add(new ArrayList<>(path));}return;}for(int i = startIndex; i <=9 ; i++){path.add(i);backingTrace(k,n,i + 1,sum +i);path.removeLast();}}
}17、电话号码的字母组合
积累下StringBuilder的几个方法，添加元素append，删除元素deleteCharAt（index）
class Solution {String[] numbers = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"
};List<String> res = new ArrayList<>();StringBuilder sb = new StringBuilder();public List<String> letterCombinations(String digits) {if(digits == null || digits.length() == 0) return res; int[] digitsArr = new int[digits.length()];for(int i = 0; i < digitsArr.length; i++){int temp = digits.charAt(i) - '0';digitsArr[i] = temp;System.out.println(temp);}backingTrace(digitsArr,0);return res;}private void backingTrace(int[] digits,int index){if(index == digits.length){res.add(sb.toString());return;}//电话号码的第index位int inNum = digits[index];for(int i = 0; i < numbers[inNum].length(); i++){char cur = numbers[inNum].charAt(i);sb.append(cur);backingTrace(digits,index + 1);sb.deleteCharAt(sb.length() - 1);}}
}//二刷class Solution {String[] numbers = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};List<String> res = new ArrayList<>();StringBuilder sb = new StringBuilder();public List<String> letterCombinations(String digits) {int n = digits.length();if(n == 0) return res;int[] nums = new int[digits.length()];for(int i = 0; i < digits.length();i++){nums[i] = (int)(digits.charAt(i) -'0');System.out.println(nums[i]);}backingTrace(n,nums);return res;}private void backingTrace(int n, int[] nums){if(sb.length() == n){res.add(new String(sb));return;}//当前遍历到电话号码的位置索引int location = sb.length();//当前遍历到的电话号码数字int locationNum = nums[location];//遍历数字按键对应的3-4个字母for(int i = 0; i < numbers[locationNum].length(); i++){//添加字母sb.append(numbers[locationNum].charAt(i));backingTrace(n,nums);sb.deleteCharAt(sb.length() - 1);}}}
