首页 > 代码库 > LeetCode: Permutations II 解题报告

LeetCode: Permutations II 解题报告

2024-08-05 23:21:38   217人阅读

Permutations II

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].

SOLUTION 1:

还是经典的递归模板。需要处理的情况是：我们先把Num排序，然后只能连续地选，这样就可以避免生成重复的solution.
例子：1 2 3 4 4 4 5 6 7 8
444这个的选法只能:4, 44, 444连续这三种选法

我们用一个visit的数组来记录哪些是选过的。

 1 public class Solution { 2     public List<List<Integer>> permuteUnique(int[] num) { 3         List<List<Integer>> ret = new ArrayList<List<Integer>>(); 4         if (num == null || num.length == 0) { 5             return ret; 6         } 7          8         // For deal with the duplicate solution, we should sort it. 9         Arrays.sort(num);10         boolean[] visit = new boolean[num.length];11         12         dfs(num, new ArrayList<Integer>(), ret, visit);13         14         return ret;15     }16     17     public void dfs(int[] num, ArrayList<Integer> path, List<List<Integer>> ret, boolean[] visit) {18         int len = num.length;19         if (path.size() == len) {20             ret.add(new ArrayList<Integer>(path));21             return;22         }23         24         for (int i = 0; i < len; i++) {25             // 只能连续地选，这样就可以避免生成重复的solution.26             // 例子：1 2 3 4 4 4 5 6 7 827             // 444这个的选法只能:4, 44, 444连续这三种选法28             if (visit[i] || (i != 0 && visit[i - 1] && num[i] == num[i - 1])) {29                 continue;30             }31             32             // 递归以及回溯33             visit[i] = true;34             path.add(num[i]);35             dfs(num, path, ret, visit);36             path.remove(path.size() - 1);37             visit[i] = false;38         }39     }40 }
View Code

GITHUB:

https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/permutation/PermuteUnique.java

LeetCode: Permutations II 解题报告


联系
我们