回溯

回溯

树形结构进行穷举
解决的问题
    - 组合（从 N 个数里找 K 个数的集合）  ==> 无序
    - 分割（将字符进行分割）
    - 子集（从 N 个数里找符合条件的子集）
    - 排列（N 个数的排列方式）             ==> 有序
    - 棋盘（N 皇后）

在集合中查找子集，集合的大小构成树的宽度，递归的深度构成树的深度

方法：
    确定返回值和参数
    终止条件
    遍历过程

    void recall(参数) {
        if (终止条件) {
            xxx
            return;
        }
        
        for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
            处理节点;
            recall(路径，选择列表); // 递归
            回溯，撤销处理结果
        }
    }
    

组合问题

    // lc77
    public List<List<Integer>> combine(int n, int k) {
        recall(n, k, 1);
        return res;
    }

    /**
     * 1  2  3  4
     *         1             2         3     4
     *    2    3    4     3     4      4
     *   12    13   14    23    24     34
     */
    public void recall(int n, int k, int start) {
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i <= n; i++) {
            path.add(i);
            recall(n, k, i + 1);
            path.remove(path.size() - 1);
        }
    }

    /**
     * 1  2  3  4
     *         1             2         3     4（剪枝）
     *    2    3    4     3     4      4
     *   12    13   14    23    24     34
     */
    public void recall2(int n, int k, int start) {
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }
        // 剪枝优化, 如果 i 已经是 4 了， 就没有必要往下遍历了
        // 还能选 k - size 个
        for (int i = start; i <= n - (k - path.size()) + 1; i++) {
            path.add(i);
            recall(n, k, i + 1);
            path.remove(path.size() - 1);
        }
    }
    
    // lc216
        public List<List<Integer>> combinationSum3(int k, int n) {
        path = new ArrayList<>(k);
        dfs(k, n, 0,1);
        return res;
    }

    public void dfs(int k, int n, int pathSum, int start) {
        // 剪枝
        if (n < pathSum) {
            return;
        }
        if (path.size() == k) {
            if (pathSum == n) {
                res.add(new ArrayList<>(path));
            }
            return;
        }
        for (int i = start; i <= 9; i++) {
            path.add(i);
            pathSum += i;
            dfs(k, n, pathSum, i + 1);
            pathSum -= i;
            path.remove(path.size() - 1);
        }
    }

分割问题

    lc131
    public List<List<String>> partition(String s) {
        dfs(s, 0);
        return res;
    }

    // aab   a|a|b|  aa|b|  aab|
    private void dfs(String s, int startIndex) {
        if (startIndex >= s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            if (isPalindrome(s, startIndex, i)) {
                String str = s.substring(startIndex, i + 1);
                path.add(str);
            } else {
                continue;
            }
            dfs(s, i + 1);
            path.remove(path.size() - 1);
        }
    }

    private boolean isPalindrome(String s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }

》 如果是一个集合来求组合的话，就需要 startIndex
》 如果是多个集合取组合，各个集合之间相互不影响，那么就不用 startIndex

子集问题

    // L78
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums)
    {
        dfs(nums, 0);
        return res;
    }

    private void dfs(int[] nums, int startIndex) 
    {
        // 记录所有
        res.add(new ArrayList<>(path));
        // 终止条件可不加，因为是遍历所有可能
        if (startIndex >= nums.length) 
        { 
            return;
        }
        for (int i = startIndex; i < nums.length; i++) 
        {
            path.add(nums[i]);
            dfs(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }

排列问题

    // L46
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;

    public List<List<Integer>> permute(int[] nums) {
        if (nums == null || nums.length == 0)
            return res;
        used = new boolean[nums.length];
        dfs(nums);
        return res;
    }

    private void dfs(int[] nums) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            dfs(nums);
            used[i] = false;
            path.remove(path.size() - 1);
        }
    }