IT技术博客大学习 共学习 共进步

标签：位掩码

共 1 篇相关文章

IT 累计浏览 3

算法模式：子集

在上一篇文章 算法模式：回溯 介绍一种“一步三回头”、“落棋有悔”的算法模式：回溯。本篇文章，介绍一种无需“一步三回头”，无需“落棋有悔”也可以解决排列组合问题的算法模式：子集。

子集

超级多的编程面试问题都会涉及到排列和组合问题。一般都是使用回溯来解决该类问题，回溯法属于 深度优先搜索。子集问题模式讲的是用 广度优先搜索 来处理这些问题。子集模式适用于子集与全排列。下面分别介绍：

处理子集问题

举例来说明一下这个模式：

给一组数字 [1, 5, 3]

  1. 我们从空集开始：[[]]

  2. 把第一个数 1，加到之前已经存在的集合中：[[], [1]];

  3. 把第二个数 5，加到之前的集合中得到：[[], [1], [5], [1,5]];

  4. 再加第三个数 3，则有：[[], [1], [5], [1,5], [3], [1,3], [5,3], [1,5,3]].

如果原有集合中存在重复元素，那么就需要针对这种情况特殊处理一下。流程如下：

给一组数字 [5, 1, 5]

  1. 先对原有集合进行排序： [1, 5, 3]

  2. 从空集开始：[[]]

  3. 把第一个数 1，加到之前已经存在的集合中：[[], [1]];

  4. 把第二个数 5，加到之前的集合中得到：[[], [1], [5], [1,5]];

  5. 处理第三个数，也是 5 时需要注意：

    1. 如果还是按照上述方案处理，那么就会得到如下结果： [[], [1], [5], [1,5], [5], [1, 5], [5, 5], [1,5, 5]]。这里出现了重复子集： [5], [1, 5]。该方案不通过，❌

    2. 观察最后生成的所有子集与重复的子集，会发现重复的子集，在处理第二个数时，已经处理过 [], [1]，如果再次处理 5，那么就会出现重复。所以，只需要处理在处理上一个相同的数时新增加的子集即可。上一个相同数新增的子集是 [5], [1,5]，只需要在这些子集后面增加当前数字即可。这样最后的子集就是：[[], [1], [5], [1,5], [5, 5], [1,5, 5]]。方案通过 ✅