力扣labuladong一刷day64天回溯大集合

力扣labuladong一刷day64天回溯大集合

先说方法论：

回溯一共就三类，分为组合、子集、排列。其中组合与子集又是一个问题，只不过子集还会搜集非叶子节点，但本质都是组合。
这三类又有其他变体，变体主要就是约束条件，共有三类：
①、元素无重，不可重复选。
②、元素可重，不可重复选。
③、元素无重，可重复选。

再给出回溯模板

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

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

之后要考虑的就是剪枝、去重，最后回溯就这点东西。

一、77. 组合

题目链接：https://leetcode.cn/problems/combinations/description/
思路：最经典的组合，直接套模板，元素不能重复使用，故每次for循环起始位置需要加1，最后可以剪枝优化一下。

class Solution {
    List<List<Integer>> arrayLists;
    List<Integer> list;
    public List<List<Integer>> combine(int n, int k) {
        arrayLists = new ArrayList<>();
        list = new ArrayList<>();
        backTracking(n, k, 1);
        return arrayLists;
    }
    void backTracking(int n, int k, int i) {
        if (list.size() == k) {
            arrayLists.add(new ArrayList<>(list));
            return;
        }
        for (int j = i; j <= n && n - (k-list.size()) + 1>= j; j++) {
            list.add(j);
            backTracking(n, k, j+1);
            list.remove(list.size()-1);
        }
    }
}

二、216. 组合总和 III

题目链接：https://leetcode.cn/problems/combination-sum-iii/description/

class Solution {
   List<List<Integer>> arrayLists;
    ArrayList<Integer> list;
    int sum = 0;
    public List<List<Integer>> combinationSum3(int k, int n) {
        arrayLists = new ArrayList<>();
        list = new ArrayList<>();
        backTracking(k, n, 1);
        return arrayLists;
    }

    void backTracking(int k, int n, int i) {
        if (sum > n) return;
        if (list.size() == k) {
            if (sum == n) {
                arrayLists.add(new ArrayList<>(list));
            }
            return;
        }
        for (int j = i; j <= 9 && sum + j <= n; j++) {
            sum+=j;
            list.add(j);
            backTracking(k, n, j+1);
            sum-=j;
            list.remove(list.size()-1);
        }
    }
}