给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

k==n，只有一个结果。因为组合不考虑顺序。

如果是返回结果有多少种，利用组合公式即可。

class Solution {

        List<List<Integer>> res = new ArrayList<>();
        public List<List<Integer>> combine(int n, int k) {
            if (k <= 0 || n < k) {
                return res;
            }
            Deque<Integer> path = new ArrayDeque<>();
            dfs(n, k, 1, path);
            return res;
        }

        private void dfs(int n, int k, int begin, Deque<Integer> path) {
            // 递归终止条件是：path 的长度等于 k
            if (path.size() == k) {
                res.add(new ArrayList<>(path));
                return;
            }
            // 遍历可能的搜索起点
//            for (int i = begin; i <= n; i++) {
                // 剪枝后   代码时间16ms -> 1ms
//                剪枝代码
            for (int i = begin; i <=  n - (k - path.size()) + 1; i++) {
                // 向路径变量里添加一个数
                path.addLast(i);
                // 下一轮搜索，设置的搜索起点要加 1，因为组合数理不允许出现重复的元素
                dfs(n, k, i + 1, path);
                // 重点理解这里：深度优先遍历有回头的过程，因此递归之前做了什么，递归之后需要做相同操作的逆向操作
                path.removeLast();
            }
        }

    }

(k – path.size()) 代表还有几位数就凑够k位数了用来剪枝。

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 – 9 的正整数，并且每种组合中不存在重复的数字。

本题就是在[1,2,3,4,5,6,7,8,9]这个集合中找到和为n的k个数的组合。因为有和的限制，所以加一个sum判断，因为是正整数所以可以有两处剪枝的地方。

class Solution {

        List<List<Integer>> res = new ArrayList<>();
        public List<List<Integer>> combinationSum3(int k, int n) {
            if (n <= 0 || n > 45) {
                return res;
            }
            Deque<Integer> path = new ArrayDeque<>();
            dfs(n, k, 0, 1, path);
            return res;
        }
        private void dfs(int target, int k, int sum, int begin, Deque<Integer> path) {
            if(sum > target) return; // 剪枝
            if (path.size() == k) {
                if(sum == target){
                    res.add(new ArrayList<>(path));
                    return;
                }
            }
            for (int i = begin; i <=  9 - (k - path.size()) + 1; i++) {// 剪枝
                path.addLast(i);
                sum += i;
                dfs(target, k, sum, i + 1, path);
                sum -= i;
                path.removeLast();
            }
        }

    }

电话号码

这道题需要收集树的所有子节点的值，无法剪枝。正常回溯即可。

class Solution {
        List<String> res = new ArrayList<>();
        String[] strs = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        public List<String> letterCombinations(String digits) {
            int n = digits.length();
            if(n==0) return res;
            StringBuilder s = new StringBuilder();
            dfs(digits,0,n,s);
            return res;
        }

        public void dfs(String digits,int index,int n,StringBuilder s){
            if(index==n){
                res.add(s.toString());
                return;
            }
            int num = digits.charAt(index) - '0';
            String str = strs[num];//'abc'
            for (int i = 0; i < str.length(); i++) {
                s.append(str.substring(i,i+1));
                dfs(digits,index+1,n,s);
                s.replace(s.length()-1,s.length(),"");
            }

        }
    }

给定⼀个⽆重复元素的数组 candidates 和⼀个⽬标数 target ，找出 candidates 中所有可以使数字和为

target 的组合。

candidates 中的数字可以⽆限制重复被选取

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int len = candidates.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }
        // 排序是剪枝的前提
        Arrays.sort(candidates);
        Deque<Integer> path = new ArrayDeque<>();
        dfs(candidates, 0, len, target, path, res);
        return res;
    }

    private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {
        // 由于进入更深层的时候，小于 0 的部分被剪枝，因此递归终止条件值只判断等于 0 的情况
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = begin; i < len; i++) {
            // 重点理解这里剪枝，前提是候选数组已经有序，
            if (target - candidates[i] < 0) {
                break;// 当前这一支全都pass
            }
            path.addLast(candidates[i]);// path存放当前已经选择的队列
            dfs(candidates, i, len, target - candidates[i], path, res);
            path.removeLast();
        }
    }


}

candidates中的每个数字在每个组合中只能使用一次。

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (candidates.length == 0) {
            return res;
        }
        // 排序是剪枝的前提
        Arrays.sort(candidates);
        Deque<Integer> path = new ArrayDeque<>();
        dfs(candidates, 0, target, path, res);
        return res;
    }

    private void dfs(int[] candidates, int begin, int target, Deque<Integer> path, List<List<Integer>> res) {
        // 由于进入更深层的时候，小于 0 的部分被剪枝，因此递归终止条件值只判断等于 0 的情况
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = begin; i < candidates.length; i++) {
            // 重点理解这里剪枝，前提是候选数组已经有序，
            if (target - candidates[i] < 0) {
                break;// 当前这一支全都pass
            }
            if(i>begin && candidates[i] == candidates[i-1] ){
                continue;//这样就不会有重复的组合 
            } // i>begin 不能省略，因为 1 1 2 这种情况同一个路径上 第一个数字不需要判断
            path.addLast(candidates[i]);// path存放当前已经选择的队列
            dfs(candidates, i+1, target - candidates[i], path, res);
            path.removeLast();
        }
    }
}

131.分割回⽂串

class Solution {
        List<List<String>> res = new ArrayList<>();
        List<String> tmp = new ArrayList<>();
        public List<List<String>> partition(String s) {
            dfs(s);
            return res;
        }
        public void dfs(String s){
            if(s.length()==0){
                res.add(new ArrayList<>(tmp));
            }
            for (int i = 1; i <= s.length(); i++) {
                String str = s.substring(0,i);
                if(isValid(str)){// 如果当前子串中的一半是回文 那么递归后半部分
                    tmp.add(str);
                    String s1 = s.substring(i);//从i开始到末尾
                    dfs(s1);
                    tmp.remove(tmp.size()-1);
                }
            }
        }
        public boolean isValid(String str){
            int n = str.length();
            for (int i = 0; i < n; i++) {
                if(str.charAt(i)!=str.charAt(n-1-i)){
                    return false;
                }
            }
            return true;
        }
    }

93.复原IP地址

class Solution {
        List<String> res = new ArrayList<>();
        public List<String> restoreIpAddresses(String s) {
            Deque<String> path = new ArrayDeque<>(4);
            dfs(s,0,path);
            return res;
        }

        public void dfs(String s, int num, Deque<String> path){
            if(num==4){// 达到了4个，达到了ip地址的上限。
                res.add(String.join(".", path));
                return;
            }
            int needmax = (3-num) * 3; // 比如当前 num = 2 说明 已经有两个整数了，这两个整数至少占了2位，
            // 那么剩余的两个整数最多占用6位，如果剩余的字符数是7 8 9 那么一定会有一个ip的整数是4位 不符合条件
            for (int i = 1; i<=3 && i <= s.length(); i++) {
                String str0 = s.substring(0,i);// 依次取当前字符串的前1个  前2个  前3个

                if(s.substring(i).length() > needmax)continue;// 剪枝
                if(str0.startsWith("0") && str0.length()>1) continue;// 01 05 06 这种字符串跳过

                int ip = Integer.valueOf(str0);
                if(ip<=255 && ip>=0){
                    path.addLast(str0);
                    String str = s.substring(i);
                    dfs(str,num+1,path);
                    path.removeLast();
                }

            }
        }
    }

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/92857.html