简介

解决组合问题需要理解回溯题型的模板。降低多次for搜索的时间复杂度。

时间复杂度：O(2^n)，组合问题其实就是一种子集的问题，所以组合问题最坏的情况，也不会超过子集问题的时间复杂度。
空间复杂度：O(n)，和子集问题同理。

第77题. 组合

题目描述

解题思路
此题注意返回的搜索的组合数不能是相反的，也因为给出的整数n也不是重复的，所以去重也不需要，下一个for也不能选择上一次的数组，所以startIndex递归时需要加一，所以直接套用回溯模板即可。
递归函数的返回值以及参数

在这里要定义两个全局变量，一个用来存放符合条件单一结果，一个用来存放符合条件结果的集合。
每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex。

回溯函数终止条件

什么时候到达所谓的叶子节点了呢？
path这个数组的大小如果达到k，说明我们找到了一个子集大小为k的组合了，在图中path存的就是根节点到叶子节点的路径。

单层搜索的过程

回溯法的搜索过程就是一个树型结构的遍历过程，在如下图中，可以看出for循环用来横向遍历，递归的过程是纵向遍历。

剪枝操作

接下来看一下优化过程如下：

已经选择的元素个数：path.size();
还需要的元素个数为: k - path.size();
在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历

为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。
举个例子，n = 4，k = 3，目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。
从2开始搜索都是合理的，可以是组合[2, 3, 4]。
注意：减去的是超过k的数字，所以减去的是怎么都选不到的，注意加一操作通过举例即可，这便是选择固定个数的剪枝通用操作。

public List<List<Integer>> combine(int n, int k) {
    backtracking(n, k, 1);
    return res;
}
List<List<Integer>> res = new ArrayList<>();   // 记录所有组合结果
LinkedList<I    nteger> path = new LinkedList<>(); // 记录一条路径
/**
         * 递归函数
         *
         * @param n          共有多少个数
         * @param k          已经选择的个数
         * @param startIndex 每次for开始遍历的索引
         */
public void backtracking(int n, int k, int startIndex) {
    // 终止条件，路径大小等于要选择大小的时候满足条件
    if (path.size() == k) {
        res.add(new ArrayList<>(path));
        return;
    }
    // 剪枝操作 k - path.size() 为未选择了，(n - (k - path.size()) + 1)表示至多要从那里开始遍历
    // + 1表示当元素也算
    for (int i = startIndex; i <= (n - (k - path.size()) + 1); i++) {
        path.add(i);
        backtracking(n, k, i + 1);
        path.removeLast();  // 回溯
    }
}

216.组合总和III

题目描述

解题思路

此题就是求总和，

确定递归函数参数

path和res和上题一样
接下来还需要如下参数：

targetSum（int）目标和，也就是题目中的n。
k（int）就是题目中要求k个数的集合。
sum（int）为已经收集的元素的总和，也就是path里元素的总和。
startIndex（int）为下一层for循环搜索的起始位置。
- 确定终止条件

所以如果path.size() 和 k相等了，就终止。
如果此时path里收集到的元素和（sum）和targetSum（就是题目描述的n）相同了，就用result收集当前的结果。

单层搜索过程

本题和77. 组合区别之一就是集合固定的就是9个数[1,…,9]，所以for循环固定i<=9

剪枝操作

此处注意不能使用上一题的剪枝操作，应为需要求的是1~9中满足sum的结果集，所以在下一次总和已经大于target时不需要在遍历一层中的后边。由于是对一层操作，所以在for上做文章。

public List<List<Integer>> combinationSum3(int k, int n) {
    backtracking(n, k, 0, 1);
    return res;
}
List<List<Integer>> res = new ArrayList<>();   // 记录所有组合结果
LinkedList<Integer> path = new LinkedList<>(); // 记录一条路径
public void backtracking(int n, int k, int sum, int startIndex) {
    // 剪枝，此时sum大于条件不满足
    if (sum > n) {
        return;
    }
    if (path.size() == k) { // 如果遍历到叶子节点，那么就算没找到结果也要return
        if (sum == n) { // 如果找到了结果
            res.add(new ArrayList<>(path));
        }
        return;
    }
    // 剪枝
    for (int i = startIndex; i <= (9 - (k - path.size()) + 1); i++) {
        sum += i;
        path.add(i);
        backtracking(n, k, sum, i + 1);
        sum -= i;   // 回溯
        path.removeLast();
    }
}

17.电话号码的字母组合

题目描述

解题思路

注意此题依旧可以按照77题的模板进行操作，单词提最主要的for开始的位置是从0开始，因为是多个字符串搜索，而不是只对一个字符串搜索。也就是求不同集合之间的组合，for起始从0开始。
数字和字符串的映射问题使用数组即可。注意：输入1 * #按键等等异常情况

确定回溯函数参数

首先需要一个字符串s来收集叶子节点的结果，然后用一个字符串数组result保存起来，这两个变量我依然定义为全局。
再来看参数，参数指定是有题目中给的string digits，然后还要有一个参数就是int型的index。
注意这个index可不是 77.组合和216.组合总和III中的startIndex了。
这个index是记录遍历第几个数字了，就是用来遍历digits的（题目中给出数字字符串），同时index也表示树的深度。

确定终止条件

例如输入用例”23”，两个数字，那么根节点往下递归两层就可以了，叶子节点就是要收集的结果集。
那么终止条件就是如果index 等于输入的数字个数（digits.size）了（本来index就是用来遍历digits的）。
然后收集结果，结束本层递归。

确定单层遍历逻辑

首先要取index指向的数字，并找到对应的字符集（手机键盘的字符集）。注意for的起始位置。

public List<String> letterCombinations(String digits) {
    if (digits.length() == 0) { // 判断""的情况
        return res;
    }
    // 初始对应所有的数字，为了直接对应2-9，新增了两个无效的字符串""
    String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    backtracking(digits, numString, 0);
    return res;
}
List<String> res = new ArrayList<>();
StringBuffer sb = new StringBuffer();
public void backtracking(String digits, String[] numString, int index) {
    if (index == digits.length()) {
        res.add(String.valueOf(sb));
        return;
    }
    String digit = numString[digits.charAt(index) - '0'];   // 获取按键映射
    for (int i = 0; i < digit.length(); i++) {
        sb.append(digit.charAt(i));
        // 注意一定要加一，获取下一个 按键
        backtracking(digits, numString, index + 1);
        sb.deleteCharAt(sb.length() - 1);   // 回溯
    }
}

39. 组合总和

题目描述

解题思路

本题和77.组合，216.组合总和III和区别是：本题没有数量要求，可以无限重复，但是有总和的限制，所以间接的也是有个数的限制。此题题目给的数组是不重复的，在搜索时也没有固定的k限制，但是有sum间接限制，而且主要的for一层遍历的开始的可以选择上一次的元素。

递归函数参数

需要res，path和一个记录总和的sum（也可以使用减法）
如果是一个集合来求组合的话，就需要startIndex，例如：77.组合，216.组合总和III。
如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：17.电话号码的字母组合

递归终止条件

从叶子节点可以清晰看到，终止只有两种情况，sum大于target和sum等于target。

单层搜索的逻辑

单层for循环依然是从startIndex开始，搜索candidates集合。
注意本题和77.组合、216.组合总和III的一个区别是：本题元素为可重复选取的。

剪枝操作

其实如果已经知道下一层的sum会大于target，就没有必要进入下一层递归了。
那么可以在for循环的搜索范围上做做文章了。
对总集合排序之后，如果下一层的sum（就是本层的 sum + candidates[i]）已经大于target，就可以结束本轮for循环的遍历。
在求和问题中，排序之后加剪枝是常见的套路！

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    Arrays.sort(candidates);
    backtracking(target, candidates, 0, 0);
    return res;
}
List<List<Integer>> res = new ArrayList<>();   // 记录所有组合结果
LinkedList<Integer> path = new LinkedList<>(); // 记录一条路径
public void backtracking(int target, int[] candidates, int startIndex, int sum) {
    //            if (sum > target) {   // 后面通过for优化操作，少一轮递归
    //                return; // 总和已经大于sum时，停止递归
    //            }
    if (target == sum) {
        res.add(new ArrayList<>(path));
        return;
    }
    // 优化操作：下一轮加上本轮已经大于target时，不进行递归
    // 注意要进行排序，否则大的数在前面后漏掉结果
    for (int i = startIndex; i < candidates.length && (candidates[i] + sum) <= target; i++) {
        sum += candidates[i];
        path.add(candidates[i]);
        backtracking(target, candidates, i, sum);    // 因为可以选择重复的，所以此时下一轮递归起始位置包括本身
        sum -= candidates[i];
        path.removeLast();
    }
}

40.组合总和II

题目描述

解题思路

这道题目和39.组合总和如下区别：

本题candidates 中的每个数字在每个组合中只能使用一次。
本题数组candidates的元素是有重复的，而39.组合总和是无重复元素的数组candidates

步骤：

递归函数参数

与39.组合总和套路相同，此题还需要加一个bool型数组used，用来记录同一树枝上的元素是否使用过。
这个集合去重的重任就是used来完成的。

递归终止条件

与39.组合总和相同，终止条件为 sum > target 和 sum == target（可以省略，单层遍历会有剪枝
操作）。

单层搜索的逻辑

这里与39.组合总和最大的不同就是要去重了。
前面我们提到：要去重的是“同一树层上的使用过”，如果判断同一树层上元素（相同的元素）是否使用过了呢。
如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]。
此时for循环里就应该做continue的操作。

可以看出在candidates[i] == candidates[i - 1]相同的情况下：

used[i - 1] == true，说明同一树枝candidates[i - 1]使用过，
used[i - 1] == false，说明同一树层candidates[i - 1]使用过，原因就是回溯时，设置了false，所以第二个相同1的根本不会递归，但第三个数2的used[i-1]是false，但是和上一个数字1不相等。所以也可以被选择。

注意：树层去重的话，需要对数组排序！因为要判断和上一个元素是否相等。
总和剪枝操作：
注意sum + candidates[i] <= target为剪枝操作，在39.组合总和有讲解过！

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    Arrays.sort(candidates);
    backtracking(target, candidates, 0, 0, new boolean[candidates.length]);
    return res;
}
List<List<Integer>> res = new ArrayList<>();   // 记录所有组合结果
LinkedList<Integer> path = new LinkedList<>(); // 记录一条路径
public void backtracking(int target, int[] candidates, int startIndex, int sum, boolean[] used) {
    if (sum == target) {
        res.add(new ArrayList<>(path));
        return;
    }
    // 优化操作
    for (int i = startIndex; i < candidates.length && (sum + candidates[i]) <= target; i++) {
        // 此时遇到重复的元素，而且还被同一层的选择过，此时不需要判断
        if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
            continue;
        }
        path.add(candidates[i]);
        sum += candidates[i];
        used[i] = true;     // 标志为没有选过，注意放在if判断后边，因为used初始化全为false
        backtracking(target, candidates, i + 1, sum, used);   // 每个元素只可以使用一次
        used[i] = false;    // 回溯，标志为已选择过，只是同层标记
        sum -= candidates[i];
        path.removeLast();
    }
}

去重方法二：

使用哈希表：set这个只代表这一层是否被选择过，所以每一层都需要一个新的set记录，且不能定义为全局变量，并且不能回溯，每一层都是不一样的哈希表，但时间复杂度和空间复杂度都大于used

// 使用set，不用排序
public void backtracking(int[] candidates, int target, int sum, int startIndex) {
    if (sum == target) {
        res.add(new ArrayList<>(path));
        return;
    }
    // set这个只代表这一层是否被选择过，所以每一层都需要一个新的set记录，且不能定义为全局变量
    HashSet<Integer> set = new HashSet<>();
    // 总和去重，需要排序
    for (int i = startIndex; i < candidates.length && (candidates[i] + sum) <= target; i++) {
        // 查找这个数在本层是否被使用过
        if (!set.isEmpty() && set.contains(candidates[i])) continue;
        set.add(candidates[i]);
        sum += candidates[i];
        path.add(candidates[i]);
        backtracking(candidates, target, sum, i + 1);
        // 错误操作:
        // 此时的哈希表表只代表本层是否使用过，和下一层无关
        // 所以下一次回溯时，和本层是否选取无关系，所以不能回溯
        // 注意和前面排序之后使用used区分
        // used时整个所有数都是用used来判断，所以有关系
        // set.remove(candidates[i]); 不需要回溯
        path.removeLast();
        sum -= candidates[i];
    }
}

Peanut的算法屋

秒杀组合问题

简介

第77题. 组合

题目描述

解题思路

216.组合总和III

题目描述

解题思路

17.电话号码的字母组合

题目描述

解题思路

39. 组合总和

题目描述

解题思路

40.组合总和II

题目描述

解题思路