leetcod Permutations I and II Solution

两个连续问题,直接讨论第二种情况
问题:
Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

链接:
第一题目:https://oj.leetcode.com/problems/permutations/
第二题目:https://oj.leetcode.com/problems/permutations-ii/

I 是 给定数组,不考虑重复值,直接列出所有的情况即可,我直接用递归,广度搜索 暴力求解了
II 是 要考虑重复值的情况,广度搜索+剪枝,简单起见,我在I 的基础上建立了一棵树(类似于Trie树),用于递归过程中剪枝。
空节点为根,BFS宽度遍历,如果遍历到某一点发现其是重复值,则直接进行剪枝操作,不考虑该节点;如果是不重复结点,正常遍历,最后所有的叶子结点都是符合条件的且唯一的组合。

代码文件:
第一题目: https://github.com/clarkchen/leetcode_java/blob/master/Permutations/permu/Solution.java
第二题目: https://github.com/clarkchen/leetcode_java/blob/master/Permutations/permu2/Solution.java

发表评论

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据

关闭菜单