Day 22 回溯算法 part01

77. 组合

我的这个解法还算挺简单易懂的，还是看注释

class Solution {
    List<List<Integer>> ans = new ArrayList(); //存储最终结果集合
    List<Integer> tmp = new ArrayList(); //记录单次的path
    public List<List<Integer>> combine(int n, int k) {
        backTracking(n, k);
        return ans;
    }

    public void backTracking(int n, int k){ //从1~n挑选k个数组合的方法
        if(n < k) return;  //若k > n 显然，不存在这样的组合
        if(k == 1){  //从n个数中挑选一个
            for(int i = n; i > 0; i--){  //对于1~n任选一个添加到结果中即可
                tmp.add(i);
                ans.add(new ArrayList(tmp));
                tmp.remove(tmp.size()-1); //回溯
            }
            return;
        }
        //这里也可以添加剪枝，即n == k的时候，直接放入结果即可
        //k > 1的情况，还可以分成两种
        //1. 选择n，再从n-1中选择k-1个数字
        tmp.add(n);
        backTracking(n-1, k-1);
        tmp.remove(tmp.size()-1);
		//2. 不选n，从n-1中选择k个即可
        backTracking(n-1, k);
    }
}

216. 组合总和 III

与上一题的做法差不太多，但是剪枝的操作我考虑的并不完整。这里使用

class Solution {
    List<List<Integer>> ans = new ArrayList();
    List<Integer> path = new ArrayList();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backTracking(1, k, n);
        return ans;
    }

    public void backTracking(int start, int k, int sum){ //start代表了现在可以取的第一个数字
        // sum代表了还需要加多少才能符合条件
        if(path.size() > k || sum < 0) return; //sum < 0 代表当前组合的和大于目标值了
        if(path.size() == k) {
            if(sum == 0) ans.add(new ArrayList(path));
            return;
        }
        for(int i = start; i <= 9; i++){ //所有的回溯都可以抽象成树结构（多叉树）
            //for循环相当于对每个子节点进行访问，只有访问到叶子节点才进行存储结果，也就是递归的出口
            path.add(i);
            backTracking(i+1, k, sum-i);
            path.remove(path.size()-1);
        }
    }
}

17. 电话号码的字母组合

class Solution {
    List<String> res = new ArrayList();
    StringBuilder sb = new StringBuilder();
    String[] map = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations(String digits) {
        if(digits.length() == 0) return res;
        backTracking(digits, 0);
        return res;
    }
    public void backTracking(String digits, int index){ //index代表当前要处理的数字在digits中的index
        if(sb.length() == digits.length()) {
            res.add(sb.toString());
            return;
        }
        int digit = digits.charAt(index) - '0';
        String s = map[digit];
        for(char c: s.toCharArray()){
            sb.append(c);
            backTracking(digits, index+1);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}