回溯算法的五类问题：组合、排列、子集、分割、棋盘

拿到一道回溯算法题首先就要判断这是一道什么类型的题，然后再确定路径选择列表和对应的剪枝方案

一、组合问题

1. 组合

题目简述：给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。leetcode链接

思路：回溯算法解决组合问题，将回溯过程抽象为一棵树形结构
* 回溯递归函数参数：（结果集result，已选择路径，下一步的选择列表）
* 回溯递归函数体：1.判断当前已选择路径是否已满足要求，若满足则返回
* 2.遍历选择列表：选择后加入路径，递归下一步的选择列表，完毕后回溯撤销上一步路径选择，继续遍历同层中的其它路径

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        Deque<Integer> path = new ArrayDeque<>();
        //初始路径选择列表为[1, n]
        backTracking(result, path, 1, n, k);
        return result;
    }

    public void backTracking(List<List<Integer>> result, Deque<Integer> path, int s, int n, int k) {
        if(path.size() == k) {
            //路径已满足要求，返回
            result.add(new ArrayList<>(path));
            return;
        }
        //遍历选择列表[s, n]。剪枝1：顺序性剪枝，剪去[0,s)；剪枝2：此时[i, n]中至少还要k-path.size()个数，路径长度不够的分支就无需遍历了
        for(int i=s;i <= n - (k - path.size()) + 1;i++) {
            //加入选择路径
            path.add(i);
            //backTracking(已选择路径，下一步的选择列表)
            backTracking(result, path, i+1, n, k);
            //回溯，撤销上一步路径选择，继续遍历同层中的其它路径
            path.removeLast();
        }
    }

2. 组合总和 III

题目简述：找出所有相加之和为n的k个数的组合，组合中：只使用数字1到9，每个数字最多使用一次。leetcode链接

思路：回溯算法。将回溯过程抽象为一棵树形结构
* 回溯递归函数参数：(结果集result，所需路径长度k，已选择路径，已选择路径总和，下一步路径选择列表）
* 回溯递归函数体：1.若路径长度已等于k：若总和满足要求则将当前路径添加到结果集。return
* 2.遍历当前选择列表：将选择加入路径，然后递归下一步的选择列表，完毕后撤销上一步选择，继续遍历同层中的其它选择

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        Deque<Integer> path = new ArrayDeque<>();
        backTracking(result, k, path, 0, 1, n);
        return result;
    }

    public void backTracking(List<List<Integer>> result, int k, Deque<Integer> path, int sum, int begin, int n) {
        if(path.size() == k) {
            if(sum == n) {
                result.add(new ArrayList<>(path));
            }
            return;
        }
        //遍历当前选择列表[begin，9]。剪枝1：顺序性剪枝，剪去[0,begin)；剪枝2：i到9的长度不能小于还需要的路径长度k - path.size()
        for(int i=begin;i <= 9 - (k - path.size() -1);i++) {
            path.add(i);sum += i;
            if(sum > n) {
                //若总和已大于n，则同层中后续的元素更大 无需遍历，直接return
                path.removeLast();
                return;
            }
            backTracking(result, k, path, sum, i+1, n);
            path.removeLast();sum -= i;
        }
    }

二、排列问题

与组合不同的是，排列需要考虑顺序，在剪枝时不能进行顺序性剪枝，只能剪去已使用的元素。用一个boolean数组记录哪些元素已使用。

1. 全排列

题目简述：给定一个不含重复数字的数组nums ，返回其所有可能的全排列。leetcode链接
思路：回溯算法。在路径选择列表剪枝时，组合问题可进行顺序性剪枝，而排列问题只能剪去path已使用过的数据
* 用一个布尔数组标记每个数是否使用过，回溯时删除路径并将对应元素使用标记重置为false
* 回溯递归函数参数：（结果集，已选择路径，数组nums和已使用标记used构成的下一步路径选择列表）
* 回溯递归函数体：1.路径长度已达到要求，则加入结果集然后return
* 2.遍历当前选择列表：将选择加入路径，然后递归下一步选择列表，完毕后撤销上一步选择，继续遍历同层其他选择

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Deque<Integer> path = new ArrayDeque<>();
        boolean[] used = new boolean[nums.length];
        backTracking(result, path, nums, used);
        return result;
    }

    public void backTracking(List<List<Integer>> result, Deque<Integer> path, int[] nums, boolean[] used) {
        if(path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        //路径选择列表：[0, n-1]
        for(int i=0;i < nums.length;i++) {
            //可行性剪枝：已使用数据（即path中已有）略过
            if (!used[i]) {
                //添加到路径
                path.add(nums[i]);
                used[i] = true;
                //*递归下一步选择列表
                backTracking(result, path, nums, used);
                //回溯撤销上一步选择，继续遍历同层其他选择
                path.removeLast();
                used[i] = false;
            }
        }
    }

2. 全排列 II

题目简述：给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。leetcode链接

思路：回溯算法。由于有重复元素，故先对数组排序，然后在同层路径选择时去重
* 回溯递归函数参数：（结果集，已选择路径，数组nums和已使用标记used构成的下一步路径选择列表）
* 回溯递归函数体：1.路径长度已达到要求，则加入结果集然后return
* 2.遍历当前选择列表：同层去重。将选择加入路径，然后递归下一步选择列表，完毕后撤销上一步选择，继续遍历同层其他选择
* 同层选择列表去重：连续相同元素的情况下，只有在上一个是上一层使用过的，这一层才可以用这一个，否则同层就重复了

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        //要保留路径顺序，不能用HashSet
        Deque<Integer> path = new ArrayDeque<>();
        boolean[] used = new boolean[nums.length];
        backTracking(result, path, nums, used);
        return result;
    }

    public void backTracking(List<List<Integer>> result, Deque<Integer> path, int[] nums, boolean[] used) {
        if(path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        //路径选择列表：[0, n-1]
        for(int i=0;i < nums.length;i++) {
            //可行性剪枝：已使用数据略过
            if (!used[i]) {
                //可行性剪枝：同层选择列表去重：若nums[i]与上一个元素值相同且上一个元素没有使用过，则略过nums[i]
                //意思就是说连续相同元素的情况下，只有在上一个是上一层使用过的，这一层才可以用这一个，否则同层就重复了
                if (i > 0 && nums[i] == nums[i-1] && !used[i-1])
                    continue;
                path.add(nums[i]);
                used[i] = true;
                backTracking(result, path, nums, used);
                path.removeLast();
                used[i] = false;
            }
        }
    }

三、子集问题

子集问题与组合问题类似，都是用集合中的元素看可以有哪些不同的组合，但是子集中不需要有集合中全部元素，可称之为子组合问题。

1. 子集

题目简述：给你一个整数数组nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集，包括空集）。leetcode链接

思路：回溯算法。关键点：每遍历到一个不同的路径都要将path加入结果集
* 回溯递归函数参数：（结果集，已选择路径，下一步路径选择列表：数组nums中下标begin开头的子数组）
* 回溯递归函数体：1.若begin==length，则数组已遍历完 直接return
* 2.遍历当前选择列表[begin,length-1]：将选择加入路径，将path加入结果集，
* 然后递归下一步选择列表，完毕后撤销上一步选择，继续遍历同层其他选择

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());
        Deque<Integer> path = new ArrayDeque<>();
        backTracking(result, path, nums, 0);
        return result;
    }

    public void backTracking(List<List<Integer>> result, Deque<Integer> path, int[] nums, int begin) {
        if(begin == nums.length) return;
        //顺序性剪枝：剪去[0, begin)
        for(int i = begin;i < nums.length;i++) {
            path.add(nums[i]);
            result.add(new ArrayList<>(path));
            backTracking(result, path, nums, i+1);
            path.removeLast();
        }
    }

2. 子集 II

题目简述：给你一个整数数组nums，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集，包括空集）。leetcode链接

这题与子集的不同之处在于，如果按照一般的回溯遍历过程，可能会出现[1,2,3] [1,3,2]这样的重复子集，或者一次路径选择列表中有多个相同元素。故需先对数组进行排序，并且在路径选择列表中进行去重，使得路径都是升序排列且不会重复选择相同路径，这样就避免了重复序列
思路：回溯算法。关键点在于要先对数组排序（避免出现[1,2,3] [1,3,2]这样的重复子集），然后对同层选择列表去重
* 回溯递归函数参数：（结果集，已选择路径，下一步路径选择列表：数组nums中下标begin开头的子数组）
* 回溯递归函数体：1.若begin==length，则数组已遍历完 直接return
* 2.遍历当前选择列表[begin,length-1]：同层去重，若与同层前一个元素相同则略过。否则将选择加入路径，将path加入结果集，
* 然后递归下一步选择列表，完毕后撤销上一步选择，继续遍历同层其他选择

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        //先排序
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());
        Deque<Integer> path = new ArrayDeque<>();
        backTracking(result, path, nums, 0);
        return result;
    }

    public void backTracking(List<List<Integer>> result, Deque<Integer> path, int[] nums, int begin) {
        if(begin == nums.length) return;
        for(int i = begin;i < nums.length;i++) {
            //每一步的路径选择列表去重，注意路径列表是从begin开始
            //因为已经排序过了，故只需要看这个路径元素与前一个元素是否相同，若相同则略过
            if(i > begin && nums[i] == nums[i-1]) continue;
            path.add(nums[i]);
            result.add(new ArrayList<>(path));
            backTracking(result, path, nums, i+1);
            path.removeLast();
        }
    }

四、分割问题

分割问题是将元素集合按照特定要求分割为多个集合。按照分割要求可分为连续分割问题（下1、2题）和非连续分割问题（下第3题）。非连续分割问题通常也可以用背包算法解决

1. 分割回文串

题目简述：给你一个字符串s，请你将s分割成一些子串，使每个子串都是回文串。返回s所有可能的分割方案。leetcode链接

思路：回溯算法。关键点在于每一步的选择列表为以begin开头切子串的方式[begin, i]，尾标i范围[begin,length-1]
* 回溯递归函数参数：（结果集，已选择路径，下一步路径选择列表：s中以下标begin开头的子串）
* 回溯递归函数体：1.若begin==length，说明已切完，则path加入结果集然后return
* 2.遍历当前选择列表：若选择切出的子串[begin,i]不是回文串则直接continue遍历同层其他选择，否则将子串加入路径，然后递归下一步选择列表[i+1, length-1]，完毕后撤销上一步选择，继续遍历同层其他选择。

    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        Deque<String> path = new ArrayDeque<>();
        backTracking(result, path, s, 0);
        return result;
    }

    /**
     * 关键是能将问题求解过程抽象为树形结构
     */
    public void backTracking(List<List<String>> result, Deque<String> path, String s, int begin) {
        if(begin == s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }
        //遍历路径选择列表：begin开头的剩余子串
        for(int i=begin;i < s.length();i++) {
            String subStr = s.substring(begin, i+1);
            //剪枝，若当前选择不是回文串则直接continue
            if(!isPalindrome(subStr))
                continue;
            path.add(subStr);
            backTracking(result, path, s, i+1);
            path.removeLast();
        }
    }

    /**
     * 判断一个字符串是否为回文串：i < len/2的部分与右边的部分比较
     */
    public boolean isPalindrome(String str) {
        int len = str.length();
        for(int i=0;i < len/2;i++) {
            if(str.charAt(i) != str.charAt(len-1-i)) {
                return false;
            }
        }
        return true;
    }

2. 复原 IP 地址

题目简述：有效IP地址正好由四个整数（每个整数位于0到255之间组成，且不能含有前导0）组成，整数之间用’.'分隔。给定一个只包含数字的字符串s，用以表示一个IP地址，返回所有可能的有效IP地址。

思路：回溯算法。关键点在于每一步的选择列表为以begin开头切子串的方式[begin, i]，尾标i范围[begin,begin+2]
* 回溯递归函数参数：（结果集，已选择路径，下一步路径选择列表：s中以下标begin开头的子串）
* 回溯递归函数体：1.若剩余字符串的长度超过最大所需长度则直接return，否则若path长度已达到要求，说明已切完，则path加入结果集然后return
* 2.遍历当前选择列表：若选择切出的子串[begin,i]已经不符合ip规则，则选择列表中后续子串肯定也不符合，直接return，否则将子串加入路径，然后递归下一步选择列表[i+1, i+3]，完毕后撤销上一步选择，继续遍历同层其他选择。

    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        Deque<String> path = new ArrayDeque<>();
        backTracking(result, path, s, 0);
        return result;
    }

    public void backTracking(List<String> result, Deque<String> path, String s, int begin) {
        //若剩余字符串的长度超过最大所需长度 则直接return
        if (s.length()-begin > 3*(4- path.size())) return;
        else if (path.size() == 4) {//否则若path长度已达到要求，则添加结果
            result.add(String.join(".", path));
            return;
        }
        //路径选择列表：begin开头的长度小于等于3的子串
        for(int i=begin;i < s.length() && i <= begin+2;i++) {
            String subStr = s.substring(begin, i+1);
            //可行性剪枝：若当前子串已经不符合ip规则，则选择列表中后续子串肯定也不符合，直接return
            if ((subStr.startsWith("0") && subStr.length() > 1) || Integer.parseInt(subStr) > 255)
                return;
            path.add(subStr);
            backTracking(result, path, s, i+1);
            path.removeLast();
        }
    }

3. 划分为k个相等的子集

题目简述：给定一个整数数组nums和一个正整数k，找出是否有可能把这个数组分成k个非空子集，其总和都相等。leetcode链接

思路：回溯算法。这是非连续分割问题，结合了子集，但是不同的是可以有重复的子集
* 首先计算目标子集总和subSum，将数组进行排序，并初始化一个已使用标记数组used。然后开始递归
* 回溯递归函数参数：（已找到的子集数ck，当前子集和nowSubSum，数组nums，[0, idx]和已使用标记used构成的下一步路径选择列表）
* 回溯递归函数体：1.若找到了k个和为subSum的子集，则必然所有元素都刚好用到了，直接返回true 若nowSubSum==subSum，说明找到了一个和为subSum的子集。将nowSubSum归零ck增1然后递归继续在剩余元素中寻找子集
* 2.倒序遍历当前选择列表[0, idx]。剪枝1：已使用数据略过。剪枝2：若nowSubSum + nums[i]已经大于subSum，则略过nums[i]继续向后遍历同层其他选择寻找更小元素。然后递归下一步选择列表[0, idx-1]，完毕后撤销上一步选择，继续遍历同层其他选择。

    int subSum = 0;//目标子集总和
    int k;
    public boolean canPartitionKSubsets(int[] nums, int k) {
        this.k = k;
        int sum = 0;
        for(int num : nums) {
            sum += num;
        }
        if(sum % k != 0) return false;//若总和就不可能均分为k份，则直接返回false
        subSum = sum / k;
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        return backTracing(0, 0, nums, nums.length-1, used);
    }

    /**
     * 1. 在剩余元素中寻找一个和为subSum的子集。
     * 2. 找到后将参数归零继续在剩余元素中寻找，若找到k个则返回true
     *
     * 若最终遍历完还是没有return true，即没有找到k个和为subSum的子集，则return false;
     */
    public boolean backTracing(int ck, int nowSubSum, int[] nums, int idx, boolean[] used) {
        //若找到了k个和为subSum的子集，则必然所有元素都刚好用到了，直接返回true
        if (ck == k) return true;
        //若nowSubSum==subSum，说明找到了一个和为subSum的子集。将nowSubSum归零ck增1然后递归继续在剩余元素中寻找子集
        if (nowSubSum == subSum) return backTracing(ck+1, 0, nums, nums.length-1, used);

        //路径选择列表 子集属于组合，可进行顺序性剪枝
        for(int i = idx;i >= 0 ;i--) {
            //可行性剪枝：已使用数据略过
            if(!used[i]) {
                //剪枝：若nowSubSum + nums[i]已经大于subSum，则略过nums[i]继续向后遍历同层其他选择寻找更小元素
                if (nowSubSum + nums[i] > subSum) continue;
                used[i] = true;
                if (backTracing(ck, nowSubSum + nums[i], nums, i-1, used)) return true;
                used[i] = false;
                //下面这个剪枝有些难理解，不用这个剪枝也能过
                //剪枝：此时若nowSubSum=0，则说明此层选择是在选子集中的第一个元素 即剩余元素中的最大值，并且没有在剩余元素中找到能与这个元素进行组合的元素集。
                //      那么是不是可以考虑将它与已构好的子集中的元素进行替换呢？
                //          1.若替换出的是一个相同值元素，那还是一样的
                //          2.由于每次构造子集是从大到小选择 尽量选择剩余元素中较大元素进行构造，那么前面构造的子集中必然没有一个子集中会存在几个较小元素之和为它，不然它在前面的子集中就已经被选用了，轮不到后面的小元素
                //      因此它没办法再参与构成一个子集了，直接返回false
                if (nowSubSum == 0) return false;
            }
        }
        return false;
    }

五、棋盘问题

待续。