对于给定的可能有重复元素的数组,打印出所有数组中所有元素重新排列的所有可能的不同组合,不要求各个组合之间的顺序 例如:
给出数组[1, 2]
打印结果:
1 2
2 1
- 取出数组中的第一个元素
- 递归调用函数,将剩余元素进行重排,返回值类型为嵌套的数组
- 将取出的元素插入到重排结果中的每一个数组中的每一个位置,依次生成本次递归返回的最终的元素组合之一
- 利用哈希算法去重后,将不重复的元素组合添加到最终要返回的数组中
- 关于去重的算法,可以利用Set中元素查找过程利用了哈希算法的特性,直接根据组合中的所有元素生成一个唯一不会重复的Key,放入Set中即可
进一步探讨:
- 若组合情况太多,可将上面的Key分成两部分,构成[Key1 : [key2]]双散列(key2所在容器为Set),以避免单个散列表过大,查找耗费时间过长的问题
- 若给定数组中的元素并非简单的Int类型,可将元素依据位置转换成Int数组(新数组中的元素代表原数组中的对象的位置),对于重复元素,Int值取该元素第一次出现的位置。 将得到的Int数组放入递归函数进行重排,递归函数返回的排列组合为原数组中元素的位置索引,根据位置索引提取原数组中的元素进行打印即可