首页 > 代码库 > Permutations II

Permutations II

2024-11-15 22:35:02   202人阅读

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

参考：http://www.cnblogs.com/remlostime/archive/2012/11/13/2768816.html

思路是一样的，不过要控制一下不能出现重复的排列。先将原数组排序，然后在控制排列的序列在原来的序列一样就不会出现重复的排序了。

先对数组进行排序，这样在DFS的时候，可以先判断前面的一个数是否和自己相等，相等的时候则前面的数必须使用了，自己才能使用，这样就不会产生重复的排列了。

 

 1 import java.util.ArrayList; 2 import java.util.Arrays; 3 import java.util.List; 4  5  6 public class Solution { 7     private boolean visited[]; 8      9     public List<List<Integer>> permuteUnique(int[] num) {10         visited = new boolean[num.length];11         Arrays.sort(num);12         List<List<Integer>> result = new ArrayList<List<Integer>>();13         DFS(num, 0, result, new ArrayList<Integer>());14         15         return result;16     }17     18     private void DFS(int num[], int dep, List<List<Integer>> result, List<Integer> cur){19         if(dep == num.length){20             result.add(new ArrayList<Integer>(cur));21             return;22         }23 24         for(int i = 0; i < num.length; i++){25             if(i >0 && num[i] == num[i - 1] && visited[i - 1] == false)26                 continue;27             if(visited[i] == false)28             {29                 cur.add(num[i]);30                 visited[i] = true;31                 DFS(num,  dep + 1, result, cur);32                 cur.remove(cur.size() - 1);33                 visited[i] = false;34             }//if35         }//for36         37     }38 }

 

Permutations II


联系
我们