思维导图

回溯算法 - 图1 我们看到上面题目是分类了，但其实不用分，都是回溯，都是搜索，都是递归，都是排列组合！！下面做题不分类！！
递归问题其实就分两类：第一类：求什么的排列，比如你能不能写个全排列，再比如N皇后(N皇后，互相不攻击，其实就是求N皇后，相互不攻击的排列)，当然，排列问题比较少，大部分都是组合的问题；第二类：就是组合问题，比如N个数中选三个，它们的和是多少，再比如求一个集合的所有子集；再比如一个字符串从某处划开，然后其在字典中出现过。有些问题你看着很陌生，感觉又是什么新花样，但其其实就是排列组合问题。
我可以告诉你：排列组合的问题程序长的差不多。

求所有方案的题目(不是求个数，求个数是另一类的题目)。比如给你个棋盘，从左上角走到右下角的所有方案；给你一个字符串，让你怎么分，使其都是回文串。
注意：是所有方案，每个方案都要，不是个数，就90%是搜索的问题。对于搜索问题，100%是排列组合问题。其解法90%是递归，10%是非递归实现递归。
因此遇到一道题目是求所有方案，不要胡思乱想，比如动态规划，比如贪心法。就把它当做排列组合，就只想搜索。

模板总结

LeetCode 78 子集

子集问题，无需考虑顺序。
其实深度优先搜索、递归、回溯全都是一个概念。

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result= new ArrayList<List<Integer>>();
        // 基本判断
        if (nums == null || nums.length == 0) return result;
        List<Integer> list = new ArrayList<>();
        subsetsHelper(result, list, nums, 0);
        return result;
    }
    void subsetsHelper(List<List<Integer>> result, List<Integer> list, int[] nums, int pos) {
        result.add(new ArrayList<Integer>(list));
        for (int i = pos; i < nums.length; i++) {
            list.add(nums[i]);
            subsetsHelper(result, list, nums, i + 1);
            list.remove(list.size() - 1); // 回溯
        }
    }
}

话不多少，上图，然后体会：这就是DFS，是深搜，是搜索，是递归，是回溯，都是一个概念。

LeetCode 90 子集 II

对于有重复元素的，我们是要对数组排序的。然后还有一些路径是要剪掉的，称为剪枝。话不多说，上图：
其实就增加了排序和剪枝。

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        // 基本判断
        if (nums == null || nums.length == 0) return result;
        List<Integer> list = new ArrayList<>();
        Arrays.sort(nums);
        subsetsWithDupHelper(nums, result, list, 0);
        return result;
    }
    void subsetsWithDupHelper(int[] nums, List<List<Integer>> result, List<Integer> list, int pos) {
        result.add(new ArrayList<Integer>(list));
        for (int i = pos; i < nums.length; i++) {
            if (i != pos && nums[i] == nums[i - 1]) {
                continue;
            }
            list.add(nums[i]);
            subsetsWithDupHelper(nums, result, list, i + 1);
            list.remove(list.size() - 1);
        }
    }
}

排列组合模板总结

使用范围
● 几乎所有的搜索问题
根据具体题目要求进行改动
● 什么时候输出比如如果是排解问题：则应该是结束后，再收集
● 哪些情况需要跳过这个就是剪枝

练习

下面就是用该模板进行练习！

46. 全排列

下面就先来一道全排列

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        // 基本判断
        if (nums == null || nums.length == 0) return result;
        List<Integer> list = new ArrayList<>();
        permuteHelper(nums, result, list);
        return result;
    }
    void permuteHelper(int[] nums, List<List<Integer>> result, List<Integer> list) {
        // 递归的出口
        if (list.size() == nums.length) {
            result.add(new ArrayList<Integer>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // 剪枝
            if (list.contains(nums[i])) {
                continue;
            }
            list.add(nums[i]);
            permuteHelper(nums, result, list);
            list.remove(list.size() - 1);
        }
    }
}

见图：

注意：排列问题，函数参数不需要pos！！

47. 全排列 II

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        // 基本判断
        if (nums == null || nums.length == 0) {
            return result;
        }
        Arrays.sort(nums);
        List<Integer> list = new ArrayList<Integer>();
        permuteUniqueHelper(nums, result, list);
        return result;
    }
    void permuteUniqueHelper(int[] nums, List<List<Integer>> result, List<Integer> list) {
        // 递归出口
        if (list.size() == nums.length) {
            result.add(new ArrayList<Integer>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // 剪枝
            if (list.contains(nums[i])) { // 这个本来就是要跳过的
                continue;
            }
            if (i != 0 && nums[i] == nums[i-1]) {
                continue;
            }
            list.add(nums[i]);
            permuteUniqueHelper(nums, result, list);
            list.remove(list.size() - 1);
        }
    }
}

上面的解法是错误的，因为剪枝不成功。
要想记住那些节点是已经用过的，要借助一个boolean[] flag数组。

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        // 基本判断
        if (nums == null || nums.length == 0) {
            return result;
        }
        Arrays.sort(nums);
        List<Integer> list = new ArrayList<Integer>();
        boolean[] flag = new boolean[nums.length];
        permuteUniqueHelper(nums, result, list, flag);
        return result;
    }
    void permuteUniqueHelper(int[] nums, List<List<Integer>> result, List<Integer> list, boolean[] flag) {
        // 递归出口
        if (list.size() == nums.length) {
            result.add(new ArrayList<Integer>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // 剪枝
            if (flag[i]) { // 这个本来就是要跳过的 该节点已用过
                continue;
            }
            if (i != 0 && nums[i] == nums[i-1] && !flag[i - 1]) { // 该节点和前面(未被用过的节点)重复了
                continue;
            }
            list.add(nums[i]);
            flag[i] = true;
            permuteUniqueHelper(nums, result, list, flag);
            list.remove(list.size() - 1);
            flag[i] = false;
        }
    }
}

注意：排列问题，函数参数不需要pos！！

77. 组合

看题目就知道怎么做了。
如果list中还没有元素，即放第一个，怎么选择路呢？从1~n - k + 1
如果已经有了，怎么选择呢？从list中末尾元素的下一个到n

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        dfs(n, k, res, new ArrayList<Integer>());
        return res;
    }
    private void dfs(int n, int k, List<List<Integer>> res, List<Integer> list) {
        if (list.size() == k) {
            res.add(new ArrayList<Integer>(list));
        }
        if (list.size() == 0) {
            for (int i = 1; i <= n - k + 1; i++) {
                list.add(i);
                dfs(n , k , res, list);
                list.remove(list.size() - 1);
            }
        } else {
            for (int i = list.get(list.size() - 1) + 1; i <= n; i++) {
                list.add(i);
                dfs(n , k , res, list);
                list.remove(list.size() - 1);
            }
        }
    }
}

LeetCode 39 组合总和

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result= new ArrayList<>();
        if (candidates == null || candidates.length == 0) {
            return result;
        }
        List<Integer> path = new ArrayList<>();
        Arrays.sort(candidates);
        combinationSumHelper(candidates, result, path, target, 0);
        return result;
    }
    void combinationSumHelper(int[] candidates, List<List<Integer>> result, List<Integer> path, int target, int pos) {
        if (target == 0) {
            result.add(new ArrayList<Integer>(path));
            return;
        }
        for (int i = pos; i < candidates.length; i++) {
            target -= candidates[i];
            // 这条路没必要走了，剪掉啦
            if (target < 0) {
                return;
            }
            path.add(candidates[i]);
            combinationSumHelper(candidates, result, path, target, i);
            path.remove(path.size() - 1);
            target += candidates[i];
        }
    }
}

我们看到下面折行代码没有排序一样成功了，说明其实无需排序！

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        dfs(candidates, target, 0, res, new ArrayList<Integer>(), 0);
        return res;
    }
    private void dfs(int[] candidates, int target, int sum, List<List<Integer>> res, List<Integer> list, int index) {
        if (sum == target) {
            res.add(new ArrayList<Integer>(list));
            return; // 这个return其实不写也会通过，参考77题，当然77题也可以写。知道为什么吗？
        }
        if (sum > target) {
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            list.add(candidates[i]);
            sum += candidates[i];
            dfs(candidates, target, sum, res, list, i);
            list.remove(list.size() - 1);
            sum -= candidates[i];
        }
    }
}

40. 组合总和 II

这道题就是要排序的！！不排序的话会重复！！

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Arrays.sort(candidates);
        dfs(candidates, target, 0, res, new ArrayList<Integer>(), 0);
        return res;
    }
    private void dfs(int[] candidates, int target, int sum, List<List<Integer>> res, List<Integer> list, int index) {
        if (sum == target) {
            res.add(new ArrayList<Integer>(list));
            return;
        }
        if (sum > target) {
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            // 去重
            if (i != index && candidates[i] == candidates[i - 1]) {
                continue;
            }
            list.add(candidates[i]);
            sum += candidates[i];
            dfs(candidates, target, sum, res, list, i + 1);
            list.remove(list.size() - 1);
            sum -= candidates[i];
        }
    }
}

216. 组合总和 III

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        dfs(k, n, res, new ArrayList<Integer>(), 0, 1);
        return res;
    }

    private void dfs(int k, int n, List<List<Integer>> res, List<Integer> list, int sum, int index) {
        if (sum > n || list.size() > k) {
            return;
        }
        if (sum == n && list.size() == k) {
            res.add(new ArrayList<Integer>(list));
        }
        for (int i = index; i <= 9; i++) {
            list.add(i);
            sum += i;
            dfs(k, n, res, list, sum, i + 1);
            list.remove(list.size() - 1);
            sum -= i;
        }
    }
}

LeetCode 17 电话号码的字母组合

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> combinations = new ArrayList<String>();
        if (digits.length() == 0) {
            return combinations;
        }
        Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
        backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
        return combinations;
    }

    public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
        if (index == digits.length()) {
            combinations.add(combination.toString());
        } else {
            char digit = digits.charAt(index);
            String letters = phoneMap.get(digit);
            int lettersCount = letters.length();
            for (int i = 0; i < lettersCount; i++) {
                combination.append(letters.charAt(i));
                backtrack(combinations, phoneMap, digits, index + 1, combination);
                combination.deleteCharAt(index);
            }
        }
    }
}

131. 分割回文串

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<List<String>>();
        dfs(s.toCharArray(), 0, res, new ArrayList<String>());
        return res;
    }
    private void dfs(char[] chs, int index, List<List<String>> res, List<String> list) {
        if (index == chs.length) {
            res.add(new ArrayList<String>(list));
            return;
        }
        for (int i = index; i < chs.length; i++) {
            if (!huiwen(chs, index, i)) {
                continue;
            }
            list.add(new String(chs, index, i - index + 1));
            dfs(chs, i + 1, res, list);
            list.remove(list.size() - 1);
        }
    }

    private boolean huiwen(char[] chs, int start, int end) {
        while (start < end) {
            if (chs[start] != chs[end]) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
}

93. 复原 IP 地址

class Solution {
    public List<String> restoreIpAddresses(String s) {
        if (s ==null || s.length() == 0 || s.length() < 4) {
            return new ArrayList<String>();
        }
        List<String> res = new ArrayList<String>();
        restoreIpAddressesHelper(res, new ArrayList<String>(), s);
        return res;
    }

    void restoreIpAddressesHelper(List<String> res , List<String> path, String strNode) {
        if (path.size() == 4 && strNode.length() == 0) {
            StringBuffer sb = new StringBuffer();
            for (String p : path)
            {
                sb.append(p).append('.');
            }
            res.add(sb.substring(0, sb.length() - 1));
            return;
        }
        if ((strNode.length() == 0 || path.size() > 4)) {
            return;
        }
        for (int i = 0; i < strNode.length(); i++)
        {
            if (Integer.parseInt(strNode.substring(0, i + 1)) > 255 || (i != 0 && strNode.charAt(0) == '0')) {
                break;
            }
            path.add(strNode.substring(0, i + 1));
            restoreIpAddressesHelper(res, path, strNode.substring(i + 1, strNode.length()));
            path.remove(path.size() - 1);
        }
    }
}

51. N 皇后

题解,这个题解非常好，非常建议看看。
主要是剪枝处的逻辑
我下面这个代码是自己修订的，比如存储path用的是int[]，判断列和45°和135°用的是一行代码。
一遍敲对，就是这么娴熟！！

class Solution {
    public List<List<String>> solveNQueens(int n) {
        int[] position = new int[n];
        List<List<String>> res = new ArrayList<List<String>>();
        dfs(n, res, position, 0); // row是当前处理的行，自然是0行开始的，只是
        return res;
    }
    private void dfs(int n, List<List<String>> res, int[] position, int row) {
        if (row == n) {
            List<String> list = new ArrayList<String>();
            for (int i = 0; i < n; i++) { // 一行行处理
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < n; j++) {
                    if (position[i] == j) {
                        sb.append('Q');
                    } else {
                        sb.append('.');
                    }
                }
                list.add(sb.toString());
            }
            res.add(list);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (chessboard(row, col, position)) {
                position[row] = col;
                dfs(n, res, position, row + 1);
                // 此处不用写回溯条件，其实row已经涵盖了这个意思
            }
        }
    }
    private boolean chessboard(int row, int col, int[] position) {
        // 同时检察同列，45°和135°
        int left = col - 1, mid = col, right = col + 1;
        for (int i = row - 1; i >= 0; i--) {
            if (position[i] == left || position[i] == mid || position[i] == right) {
                return false;
            } else {
                left--;
                right++;
            }
        }
        return true;
    }
}

37. 解数独未完成

491. 递增子序列

class Solution {
    public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        dfs(nums, 0, res, new ArrayList<Integer>());
        return res;
    }
    private void dfs(int[] nums, int index, List<List<Integer>> res, List<Integer> list) {
        if (list.size() > 1) {
            res.add(new ArrayList<Integer>(list));
        }
        if (index == nums.length) {
            return;
        }
        Set<Integer> set = new HashSet<Integer>();
        for (int i = index; i < nums.length; i++) {
            /*if (i != index && nums[i] == nums[i - 1]) {
                continue;
            }*/
            if (set.contains(nums[i])) {
                continue;
            }
            set.add(nums[i]);
            if (list.isEmpty() || nums[i] >= list.get(list.size() - 1)) {
                list.add(nums[i]);
                dfs(nums, i + 1, res, list);
                list.remove(list.size() - 1);
            }
        }
    }
}

数据结构与算法(LeetCode)

回溯算法

思维导图

模板总结

LeetCode 78 子集

LeetCode 90 子集 II

排列组合模板总结

练习

46. 全排列

47. 全排列 II

77. 组合

LeetCode 39 组合总和

40. 组合总和 II

216. 组合总和 III

LeetCode 17 电话号码的字母组合

131. 分割回文串

93. 复原 IP 地址

51. N 皇后

37. 解数独未完成

491. 递增子序列

332. 重新安排行程未完成

回溯算法

思维导图

模板总结

LeetCode 78 子集

LeetCode 90 子集 II

排列组合模板总结

练习

LeetCode 39 组合总和

LeetCode 17 电话号码的字母组合

37. 解数独 未完成

332. 重新安排行程 未完成

37. 解数独未完成

332. 重新安排行程未完成