如何求数字的组合？

Nen 2022-03-29 16:38

- 程序员

打印数字的排列组合方式的最简单的方法就是递归，但本题存在两个难点：第一，数字中存在重复数字；第二，明确规定了某些位的特性。显然，采用常规的求解方法似乎不能完全适用了。其实，可以换一种思维，把求解这6个数字的排列组合问题转换为大家都熟悉的图的遍历的问题，解答起来就容易多了。可以把1、2、2、3、4、5这6个数看成是图的6个结点，对这6个结点两两相连可以组成一个无向连通图，这6个数对应的全排列等价于从这个图中各个结点出发深度优先遍历这个图中所有可能路径所组成的数字集合。例如，从结点“1”出发所有的遍历路径组成了以“1”开头的所有数字的组合。由于“3”与“5”不能相连，因此，在构造图的时候使图中“3”和“5”对应的结点不连通就可以满足这个条件。对于“4”不能在第三位，可以在遍历结束后判断是否满足这个条件。

具体而言，实现步骤如下所示。1）用1、2、2、3、4、5这6个数作为6个结点，构造一个无向连通图。除了“3”与“5”不连通外，其他的所有结点都两两相连。2）分别从这6个结点出发对图做深度优先遍历。每次遍历完所有结点的时候，把遍历的路径对应数字的组合记录下来，如果这个数字的第三位不是“4”，那么把这个数字存储到集合Set中（由于这6个数中有重复的数，因此，最终的组合肯定也会有重复的。由于集合Set的特点为集合中的元素是唯一的，不能有重复的元素，因此，通过把组合的结果存储到Set中可以过滤掉重复的组合）。3）遍历Set集合，打印出集合中所有的结果，这些结果就是本问题的答案。实现代码如下：

由于结果过多，这里只给出部分运行结果：

轩辕小不懂的其他提问

类似问题