【数据结构与算法】回溯解决组合问题

回溯法也可以叫做回溯搜索法，它是一种搜索的方式，回溯的本质就是穷举，然后选出我们想要的答案。如果题目不要求时间复杂度，回溯无疑就是最容易想到的暴力解法

动态规划问题 都可以被转化为 回溯问题 来解决，但是毫无疑问会时间超时，但是这不影响我们把它作为突破口，因为回溯只要你能够理解题意，写出正确的递归条件和跳出条件，那么一切都好解决了

例题1

https://leetcode.cn/problems/combinations/

思路

算是回溯的入门题，也是经典的组合问题

代码

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

        return ans;
    }

    private void backTracking(List<List<Integer>> ans, int n, int k, int i, List<Integer> list) {
        if (list.size() == k) {
            ans.add(new ArrayList<>(list));
            return;
        }
        for (int j = i; j <= n; j++) {
            list.add(j);
            backTracking(ans, n, k, j + 1, list);
            list.remove(list.size() - 1);
        }
    }
}

例题2

扫地机器人问题

1. A[i] 代表 第 i 个城市每天会产生的垃圾，N 表示城市数量， M 表示放置一个扫地机器人的费用
2. 扫地机器人每天完成清理会向后移动一格，比如第 1 天在 i 处放置一个扫地机器人后，i 处完成清理，扫地机器人移动至 i + 1
3. 现在给你 A[], N, M 三个参数，请你计算完成所有城市清理的最小费用

例1. A[] = {2, 4, 7, 10, 3, 4, 1}, N = 7, M = 10
如果在 i = 0, i = 3 放置两个扫地机器人，cost_0 = 20
第一天, 0, 3 完成清理, cost_1 = A[1] + A[2] + A[4] + A[5] + A[6] = 18
第二天, 1, 4 完成清理, cost_2 = A[2] + A[5] + A[6] = 9
第三天, 2, 5 完成清理, cost_3 = A[6] = 1
第四天, 6 完成清理, cost = cost_0 + cost_1 + cost_2 + cost_3 = 48

如果在 i = 0, i = 2, i = 3 放置两个扫地机器人，cost_0 = 30
第一天, 0, 2, 3 完成清理, cost_1 = A[1]  + A[4] + A[5] + A[6] = 12
第二天, 1, 4 完成清理, cost_2 = A[5] + A[6] = 5
第三天, 5 完成清理, cost_3 = A[6] = 1
第四天, 6 完成清理, cost = cost_0 + cost_1 + cost_2 + cost_3 = 48
以此类推，最小费用是 48
请你编写程序，解决该问题

思路

这道题最优的解法一定不是回溯，但是如果想用模拟法解决只能回溯，即穷举出机器人的所有放置方式，然后取最小值

代码

class Solution {
    /**
     * 扫地机器人问题
     * A[i] 代表 第 i 个城市每天会产生的垃圾，N 表示城市数量， M 表示放置一个扫地机器人的费用
     * 扫地机器人每天完成清理会向后移动一格，比如第 1 天在 i 处放置一个扫地机器人后，i 处完成清理，扫地机器人移动至 i + 1
     * 现在给你 A[], N, M 三个参数，请你计算完成所有城市清理的最小费用
     * <p>
     * 例1. A[] = {2, 4, 7, 10, 3, 4, 1}, N = 7, M = 10
     * 如果在 i = 0, i = 3 放置两个扫地机器人，cost_0 = 20
     * 第一天, 0, 3 完成清理, cost_1 = A[1] + A[2] + A[4] + A[5] + A[6] = 18
     * 第二天, 1, 4 完成清理, cost_2 = A[2] + A[5] + A[6] = 9
     * 第三天, 2, 5 完成清理, cost_3 = A[6] = 1
     * 第四天, 6 完成清理, cost = cost_0 + cost_1 + cost_2 + cost_3 = 48
     * <p>
     * 如果在 i = 0, i = 2, i = 3 放置两个扫地机器人，cost_0 = 30
     * 第一天, 0, 2, 3 完成清理, cost_1 = A[1]  + A[4] + A[5] + A[6] = 12
     * 第二天, 1, 4 完成清理, cost_2 = A[5] + A[6] = 5
     * 第三天, 5 完成清理, cost_3 = A[6] = 1
     * 第四天, 6 完成清理, cost = cost_0 + cost_1 + cost_2 + cost_3 = 48
     * 以此类推，最小费用是 48
     * 请你编写程序，解决该问题
     */

    public int minCost(int[] A, int N, int M) {
        int ans = calculate(A, new ArrayList<Integer>(){
            {
                add(0);
            }
        }, N, M);
        // 第0个机器人是必须设置的，i表示额外设置的机器人个数
        for (int i = 1; i < N; i++) {
            // 回溯处理i个机器人所有设置的方式，即i个数的从1到N-1的所有组合
            for (List<Integer> starts : getStarts(i, N-1)) {
                starts.add(0);
                ans = Math.min(ans, calculate(A, starts, N, M));
            }
        }

        return ans;
    }

    private int calculate(int[] A, List<Integer> starts, int N, int M) {
        int sum = M * starts.size();
        Set<Integer> cleans = new HashSet<>();
        while (cleans.size() < N) {
            for (int i = 0; i < starts.size(); i++) {
                int j = starts.get(i);
                cleans.add(j);
                if (j + 1 < N) {
                    starts.set(i, j+1);
                }
            }
            for (int i = 0; i < N; i++) {
                if (!cleans.contains(i)) {
                    sum += A[i];
                }
            }
        }

        return sum;
    }

    private List<List<Integer>> getStarts(int len, int end) {
        List<List<Integer>> ans = new ArrayList<>();
        backTracking(ans, new ArrayList<>(), 1, len, end);
        return ans;
    }

    private void backTracking(List<List<Integer>> ans, List<Integer> list, int start, int len, int end) {
        if (list.size() == len) {
            ans.add(new ArrayList<>(list));
            return;
        }
        for (int i = start; i <= end ; i++) {
            list.add(i);
            backTracking(ans, list, i + 1, len, end);
            list.remove(list.size() - 1);
        }
    }
}