39/40/46/47/77/78/90/60/93排列、组合、子集相关问题

39 组合总和

39. 组合总和

思路分析：根据示例 1：输入: candidates = [2, 3, 6, 7]，target = 7。

候选数组里有 2，如果找到了组合总和为 7 - 2 = 5 的所有组合，再在之前加上 2 ，就是 7 的所有组合；
同理考虑 3，如果找到了组合总和为 7 - 3 = 4 的所有组合，再在之前加上 3 ，就是 7 的所有组合，依次这样找下去。

  • 以 target = 7 为根节点，创建一个分支的时候做减法。
  • 每一个箭头表示：从父亲节点的数值减去边上的数值，得到孩子节点的数值。边的值就是题目中给出的 candidate 数组的每个元素的值。
  • 减到0或负数的时候停止，即：节点0和负数节点成为叶子节点。
  • 所有从根节点到节点0的路径（只能从上往下，没有回路）就是题目要找的一个结果

这棵树有 4 个叶子结点的值 0，对应的路径列表是 [[2, 2, 3], [2, 3, 2], [3, 2, 2], [7]]，而示例中给出的输出只有 [[7], [2, 2, 3]]。即：题目中要求每一个符合要求的解是 不计算顺序 的。下面我们分析为什么会产生重复。

针对具体例子分析重复路径产生的原因（难点）

产生重复的原因是：在每一个结点，做减法，展开分支的时候，由于题目中说，每一个元素可以重复使用，我们考虑了所有的候选数，因此出现了重复的列表。

一种简单的去重方案是借助哈希表的天然去重功能，但实际操作没那么容易。

另一种可以再搜索的时候去重，遇到这一类相同元素不计算顺序的问题，我们在搜索的时候就需要按某种顺序搜索。具体做法是：每一次搜索的时候设置下一轮搜索的起点 begin ：

即：从每一层的第2个节点开始，都不能再搜索产生同一层节点使用过的 candidate 里的元素。

  • Python3 的 [1, 2] + [3] 语法生成了新的列表，一层一层传到根结点以后，直接 res.append(path) 就可以了；
  • 基本类型变量在传参的时候，是复制，因此变量值的变化在参数里体现就行，所以 Python3 的代码看起来没有「回溯」这个步骤。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from typing import List
class Solution:
  	def combinationSum(self, candidates, target):
      	size = len(candidates)
        if size == 0:
          	return []
        path = []
        res = []
        def dfs(candidates, begin, size, res, target):
          	if target < 0:
              	return
            if target == 0:
              	res.append(path)
                return
            for  index in range(begin, size):
              	dfs(candidates, index, size, path+[candidates[index]], res, target - candidate[index])
        dfs(candidates, 0, size, path, res, target)
        return res
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Solution {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int len = candidates.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        Deque<Integer> path = new ArrayDeque<>();
        dfs(candidates, 0, len, target, path, res);
        return res;
    }

    private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {
        // target 为负数和 0 的时候不再产生新的孩子结点
        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 重点理解这里从 begin 开始搜索的语意
        for (int i = begin; i < len; i++) {
            path.addLast(candidates[i]);

            // 注意：由于每一个元素可以重复使用，下一轮搜索的起点依然是 i，这里非常容易弄错
            dfs(candidates, i, len, target - candidates[i], path, res);

            // 状态重置
            path.removeLast();
        }
    }
}

剪枝提速

  • 根据上面画树形图的经验，如果 target 减去一个数得到负数，那么减去一个更大的树依然是负数，同样搜索不到结果。基于这个想法，我们可以对输入数组进行排序，添加相关逻辑达到进一步剪枝的目的；
  • 排序是为了提高搜索速度，对于解决这个问题来说非必要。但是搜索问题一般复杂度较高，能剪枝就尽量剪枝。实际工作中如果遇到两种方案拿捏不准的情况，都试一下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Solution {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int len = candidates.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        // 排序是剪枝的前提
        Arrays.sort(candidates);
        Deque<Integer> path = new ArrayDeque<>();
        dfs(candidates, 0, len, target, path, res);
        return res;
    }

    private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {
        // 由于进入更深层的时候，小于 0 的部分被剪枝，因此递归终止条件值只判断等于 0 的情况
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = begin; i < len; i++) {
            // 重点理解这里剪枝，前提是候选数组已经有序，
            if (target - candidates[i] < 0) {
                break;
            }
            
            path.addLast(candidates[i]);
            dfs(candidates, i, len, target - candidates[i], path, res);
            path.removeLast();
        }
    }
}

什么时候使用 used 数组，什么时候使用 begin 变量

  • 排列问题，讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为不同列表时），需要记录哪些数字已经使用过，此时用 used 数组；
  • 组合问题，不讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为相同列表时），需要按照某种顺序搜索，此时使用 begin 变量。

40 组合总和 2

40. 组合总和 II

candidates 中的每个数字在每个组合中只能使用一次。

为了使得解集不包含重复的组合，有两种方案：

  • 使用哈希表，编码复杂
  • 需要按顺序搜索，在搜索的过程中检测分支是否会出现重复结果。注意：这里的顺序不仅仅指数组candidate有序，还指按照一定顺序搜索结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if(candidates.length==0) return res;

        int n  = candidates.length;
        Deque<Integer> path = new ArrayDeque<>();

        Arrays.sort(candidates);

        dfs(candidates, 0, n, path, target,res);
        return res;
    }


    private void dfs(int[] candidates, int begin, int n, Deque<Integer> path, int target, List<List<Integer>> res){
    
        if(target == 0){
            res.add(new ArrayList<>(path));
            return;
        }

        // 小剪枝：同一层相同数值的节点，从第2个开始，候选数更少，结果一定发生重复，因此跳过
        

        for(int i=begin;i<n;i++){
           // 大剪枝：减去 candidates[i] 小于0 ，减去后面的candidates[i+1], candidates[i+2] 肯定也小于0
           if(target - candidates[i]<0){
               break;
           }
           // 小剪枝：同一层相同数值的节点，从第2个开始，候选数更少，结果一定发生重复，因此跳过
           if(i > begin && candidates[i] == candidates[i-1]){
               continue;
           }
           path.addLast(candidates[i]);
           dfs(candidates, i+1, n, path, target - candidates[i], res);
           path.removeLast();
        }

    }

}

77 组合

77. 组合

法一：根据搜索起点画出二叉树

  • 如果组合里有 1， 那么需要再 $[2,3,4]$ 里再找一个数
  • 如果组合里有 2， 那么需要再 $[3,4]$ 里再找一个数，注意：这里不能再考虑 1，因为包含 1 的组合，在第一种情况以及包含。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public class Solution {

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        if (k <= 0 || n < k) {
            return res;
        }
        // 从 1 开始是题目的设定
        Deque<Integer> path = new ArrayDeque<>();
        dfs(n, k, 1, path, res);
        return res;
    }

    private void dfs(int n, int k, int begin, Deque<Integer> path, List<List<Integer>> res) {
        // 递归终止条件是：path 的长度等于 k
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 遍历可能的搜索起点
        for (int i = begin; i <= n; i++) {
            // 向路径变量里添加一个数
            path.addLast(i);
            // 下一轮搜索，设置的搜索起点要加 1，因为组合数理不允许出现重复的元素
            dfs(n, k, i + 1, path, res);
            // 重点理解这里：深度优先遍历有回头的过程，因此递归之前做了什么，递归之后需要做相同操作的逆向操作
            path.removeLast();
        }
    }
}

剪枝

上面的代码，搜索起点遍历到 n，即：递归函数中有下面的代码片段：

1
2
3
4
5
6
// 从当前搜索起点 begin 遍历到 n
for (int i = begin; i <= n; i++) {
    path.addLast(i);
    dfs(n, k, i + 1, path, res);
    path.removeLast();
}

事实上，如果 n=7, k=4 ，从5开始搜索就已经没有意义了， 这是因为：即使把5选上，后面的数只有，6，7一共三个候选数，凑不出4个数的组合。因此搜索起点有上界，这个上界是多少，可以举例分析。

分析搜索起点的上界，其实是在深度优先遍历的过程中剪枝，剪枝可以避免不必要的遍历，剪枝剪得好，可以大幅度节约算法的执行时间。

下面的图片绿色部分是减掉的枝叶，当n很大的时候，能少遍历很多节点，节约了时间

容易知道：搜索起点和当前还需要选几个数有关，而当前还需要选几个数与已经选了几个数有关，即与path 的长度相关。举例分析：

例如： n=6, k=4

path.size() == 1 的时候，接下来要选择 3 个数，搜索起点最大是 4，最后一个被选的组合是 [4, 5, 6]；

path.size() == 2 的时候，接下来要选择 2 个数，搜索起点最大是 5，最后一个被选的组合是 [5, 6]；

path.size() == 3 的时候，接下来要选择 1 个数，搜索起点最大是 6，最后一个被选的组合是 [6]；

再如：n = 15 ，k = 4。

path.size() == 1 的时候，接下来要选择 3 个数，搜索起点最大是 13，最后一个被选的是 [13, 14, 15]；

path.size() == 2 的时候，接下来要选择 2 个数，搜索起点最大是 14，最后一个被选的是 [14, 15]；

path.size() == 3 的时候，接下来要选择 1 个数，搜索起点最大是 15，最后一个被选的是 [15]；

可以归纳出：

搜索起点的上界 + 接下来要选择的元素个数 - 1 = n

其中，接下来要选择的元素个数 = k - path.size()，整理得到：

搜索起点的上界 = n - (k - path.size()) + 1

所以，我们的剪枝过程就是：把 i <= n 改成 i <= n - (k - path.size()) + 1 ：

1
2
3
4
5
6
// 只有这里 i <= n - (k - path.size()) + 1 与参考代码 1 不同
        for (int i = index; i <= n - (k - path.size()) + 1; i++) {
            path.addLast(i);
            dfs(n, k, i + 1, path, res);
            path.removeLast();
        }

方法二：按照每一个数选与不选画出二叉树

画一个表格更容易看出边界条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Solution {

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        if (k <= 0 || n < k) {
            return res;
        }

        // 为了防止底层动态数组扩容，初始化的时候传入最大长度
        Deque<Integer> path = new ArrayDeque<>(k);
        dfs(1, n, k, path, res);
        return res;
    }

    private void dfs(int begin, int n, int k, Deque<Integer> path, List<List<Integer>> res) {
        if (k == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 基础版本的递归终止条件：if (begin == n + 1) {
        if (begin > n - k + 1) {
            return;
        }
        // 不选当前考虑的数 begin，直接递归到下一层
        dfs(begin + 1, n, k, path, res);

        // 不选当前考虑的数 begin，递归到下一层的时候 k - 1，这里 k 表示还需要选多少个数
        path.addLast(begin);
        dfs(begin + 1, n, k - 1, path, res);
        // 深度优先遍历有回头的过程，因此需要撤销选择
        path.removeLast();
    }
}

78 子集

78. 子集

  • 组合问题，需要按顺序读字符，就不需要设置used 数组
  • 在根节点、非叶子节点和叶子节点都需要结算，因此 res.add(path)需要放中间

法一： 回溯搜索

执行一次深度优先遍历，一路走到底，走不通的时候，返回回来，继续执行，一直这样下去，知道回到起点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        
        if(nums.length==0){
            return res;
        }
        int n = nums.length;
        Deque<Integer> path = new ArrayDeque<>();

        dfs(0, n, nums, path, res);

        return res;
    }

    private void dfs(int begin, int n, int[] nums, Deque<Integer> path, List<List<Integer>> res){
        if(begin == n){
            res.add(new ArrayList<>(path));
            return;
        }
        // 当前数可选 也可以不选

        // 不选 直接进入下一层
        dfs(begin+1, n, nums, path, res);
        // 选了，进入下一层
        path.add(nums[begin]);
        dfs(begin+1, n, nums, path, res);
        path.removeLast();
    }

}

把选这个数作为左分支，把不选这个数作为右分支

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Solution {

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int len = nums.length;
        if (len == 0) {
            return res;
        }
        Stack<Integer> stack = new Stack<>();
        dfs(nums, 0, len, stack, res);
        return res;
    }

    private void dfs(int[] nums, int index, int len,
                     Stack<Integer> stack, List<List<Integer>> res) {
        if (index == len) {
            res.add(new ArrayList<>(stack));
            return;
        }
        // 当前数可选，也可以不选
        // 选了有，进入下一层
        stack.add(nums[index]);
        dfs(nums, index + 1, len, stack, res);
        stack.pop();

        // 不选，直接进入下一层
        dfs(nums, index + 1, len, stack, res);
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        Solution solution = new Solution();
        List<List<Integer>> subsets = solution.subsets(nums);
        System.out.println(subsets);
    }
}

方法二：使用位运算技巧

数组的每个元素，可以有两个状态：

  • 不在子数组中（用0表示）
  • 在子数组中（用1表示）

从0到2 的数组个数次幂（不包括）的整数的二进制表示就能表示所有状态的集合

子集数量为 $2^n$ ，也就是1 << n
用二进制0表示不选，1表示选，遍历从0到 $2^n$ 的所有二进制数
对每个二进制数也就是每种子集情况都要遍历一边nums数组，
将二进制数中为1的位置在nums中对应的数加入到当前子集中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        int size = nums.length;
        int n = 1 << size;
        
        List<List<Integer>> res = new ArrayList<>();

        for(int i =0;i<n;i++){
            List<Integer> cur = new ArrayList<>();
            for(int j=0;j<size;j++){
                if( ((i>>j) & 1) ==1){
                    cur.add(nums[j]);
                }
            }
            res.add(cur);
        }

        return res;
    }
}

90. 子集 II

90. 子集 II

解集 不能 包含重复的子集

考虑数组 $[1,2,2]$ ，选择前两个数，或者第一、三个数，都会得到相同的子集。

也就是说，对于当前选择的数 $x$ ，若前面有与其相同的数y，且没有选择 y，此时包含的 x 的子集，必然会出现在包含 y 的所有子集中。

我们可以通过判断这种情况，来避免生成重复的子集。代码实现时，可以先将数组排序；迭代时，若发现没有选择上一个数，且当前数字与上一个数相同，则可以跳过当前生成的子集。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums.length==0){
            return res;
        }
        int n = nums.length;
        Deque<Integer> path = new ArrayDeque<>();
        Arrays.sort(nums);
        dfs(0, false, n, path, nums, res);
        return res;
    }


    private void dfs(int begin,boolean choose, int n, Deque<Integer> path, int[] nums, List<List<Integer>> res){
        if(begin==n){
            res.add(new ArrayList<>(path));
            return;
        }

        dfs(begin+1, false, n,path, nums, res);

        if(begin>0 && nums[begin]==nums[begin-1] && !choose){
            return;
        }
        path.add(nums[begin]);
        dfs(begin+1, true, n, path, nums, res);
        path.removeLast();
    }
}

时间复杂度：

$O(n \times 2^n)$ 其中 n 是数组nums 的长度。排序时间复杂度为 $O(nlogn)$ 。最坏情况下nums中无重复元素，需要枚举其所有 $ 2^n$ 个子集，每个子集加入答案时需要拷贝一份，耗时 $O(n)$, 一共需要 $O(n \times 2^n) + O(n) = O(n\times 2^n)$ 的实际来构造子集。

空间： $O(n)$ , 临时数组t的空间代价是O(n)， 递归时栈空间的代价为 $O(n)$

60. 排列序列

一句话题解：以下给出两种方法，思路其实是一样的：通过 计算剩余数字个数的阶乘，一位一位选出第 k 个排列的位数。

基于以下几点考虑，

所求排列一定在叶子节点处得到，可以根据已经选定的数的个数，进而计算还未选定的数的个数，然后计算阶乘，就知道这一个分支的叶子节点的个数。

  • 如果 k 大于这一个分支将要产生的叶子节点数，直接跳过这个分支，这个操作叫剪枝。
  • 如果 k 小于等于 这个分支将要产生的叶子节点数，那说明所求的全排列一定在这个分支将要产生的叶子节点里，需要递归求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    public String getPermutation(int n, int k) {
        if(n == 0){
            return "";
        }
        boolean[] used = new boolean[n+1];
        StringBuilder path = new StringBuilder();
        int[] factorial = new int[n+1]; // 阶乘数组
        factorial[0] = 1;
        for(int i=1;i<=n ;i++){
            factorial[i] = factorial[i-1] * i;
        }

        dfs(0, n ,k, path, used, factorial);
        return path.toString();
    }

    // index 在这一步之前已经选择了几个数字，其值恰好是等于这一步需要确定的下标位置
    private void dfs(int index,int n,int k, StringBuilder path, boolean[] used, int[] factorial){
        if(index == n){
            return;
        }

        // 计算还未确定的数字的全排列的个数，第一次进入的时候是 n-1
        int cnt = factorial[n-1-index];
        for (int i=1; i<=n; i++){
            if(used[i]) continue;
            if (cnt < k){
                k -= cnt;
                continue;
            }
            path.append(i);
            used[i] = true;
            dfs(index+1, n, k, path, used, factorial);
            // 注意：不可以回溯（重置变量），算法设计是【一下子来到叶子结点】，没有回头的过程
            // 这里加return，后面的数没有必要遍历去尝试了
            return;
        }

    }

}

93. 复原 IP 地址

分析剪枝条件：

  • 一开始，字符串的长度小于4 或者 大于 12， 一定不能拼凑出合法的ip
  • 每一个节点可以选择截取的法法只有三种，截1位，截2位，截3位，因此灭一个节点可以生长出的分支最多有3条，根据截取出来的字符串判断是否是合理ip，先截取，再转成int判断。
  • 由于ip段最多就4段，因此这颗三叉树最多4层，这个条件作为递归终止条件之一。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
    public List<String> restoreIpAddresses(String s) {
        int n = s.length();
        List<String> res =  new ArrayList<>();
        if (n < 4 || n>12){
            return res;
        }
        Deque<String> path = new ArrayDeque<>(4);
        dfs(0,0, n, path, s, res);
        return res;
    }

    private void dfs(int begin, int splitTimes, int n, Deque<String> path, String s, List<String> res){
        if(begin == n){
            if(splitTimes == 4){
                res.add(String.join(".",path));
            }
            return;
        }

        // 看到剩下的不够就退出，n-begin 表示剩余的还未分割的字符串的位数
        if(n - begin < (4-splitTimes) || n - begin > 3*(4-splitTimes)){
            return;
        }

        for(int i=0;i<3;i++){
            if(begin + i >= n){
                break;
            }
            int ipSegment = judgeIFIpSegemnt(s, begin, begin+i);
            if(ipSegment != -1){
                // 在判断是ip段的情况下，采取截取
                path.addLast(String.valueOf(ipSegment));
                dfs(begin+i+1, splitTimes+1, n, path, s, res);
                path.removeLast();
            }
        }

    }


    // 判断s的子区间 [left, right] 是否能构成一个 ip段
    private int judgeIFIpSegemnt(String s, int left, int right){
        int len = right - left + 1;
        // 大于1 位的时候，不能以0开头
        if(len>1 && s.charAt(left) == '0'){
            return -1;
        }

        // 转成int 类型
        int res = 0;
        for(int i=left; i<=right; i++){
            res = res*10 + s.charAt(i) - '0';
        }

        if(res > 255){
            return -1;
        }
        return res;
    }

}