LeetCode - Permutations II | Darren's Blog

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].
Code from http://www.darrensunny.me/leetcode-permutations-ii/
with the use of a boolean array, do not consider to add a duplicate number to the next recursion if its earlier appearance has not been considered yet. This will avoid duplicate permutations.
跟 Permutations的解法一样，就是要考虑“去重”。先对数组进行排序，这样在DFS的时候，可以先判断前面的一个数是否和自己相等，相等的时候则前面的数必须使用了，自己才能使用，这样就不会产生重复的排列了。

public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {

        if (num == null)

            return null;

        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

        if (num.length == 0)

            return result;

        Arrays.sort(num);       // Sort the array in non-descending order

        recursivePermute(num, new boolean[num.length], new ArrayList<Integer>(), result);

        return result;

    }

 

    // If "current" is already a permutation of "num", add it to "result";

    // otherwise, append each unused number to "current", and recursively try next unused number

    private void recursivePermute(int[] num, boolean[] used, ArrayList<Integer> current,

                                  ArrayList<ArrayList<Integer>> result) {

        if (current.size() == num.length) {     // "current" is already a permutation of "num"

            result.add(new ArrayList<Integer>(current));

            return;

        }

        // Append each unused number to "current", and recursively try next unused number

        for (int i = 0; i < num.length; i++) {

            if (i > 0 && !used[i-1] && num[i]==num[i-1])

                // Do not consider a duplicate number if its earlier appearance has

                // not been considered yet

                continue;

            if (!used[i]) {

                // Append an unused number

                used[i] = true;

                current.add(num[i]);

                // Recursively append next unused number

                recursivePermute(num, used, current, result);

                // Get back to original state, get ready for appending another unused number

                current.remove(current.size()-1);

                used[i] = false;

            }

        }

    }

Code from http://fisherlei.blogspot.com/2012/12/leetcode-permutations-ii.html
void GeneratePermute(vector<int> & num, int step, vector<int>& visited, vector<int>& solution, vector<vector<int> >& coll)
{
  if(step == num.size())
  {
coll.push_back(solution);
return;
  }
  for(int i =0; i< num.size(); i++)
  {
if(visited[i] == 0)
{
 if(i>0 && num[i] == num[i-1] && visited[i-1] ==0)
continue;
 visited[i] = 1;
 solution.push_back(num[i]);
 GeneratePermute(num, step+1, visited, solution, coll);
 solution.pop_back();
 visited[i] =0;
}
  }
}
Code from http://www.programcreek.com/2013/02/leetcode-permutations-ii-java/

public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) { ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); permuteUnique(num, 0, result); return result; } private void permuteUnique(int[] num, int start, ArrayList<ArrayList<Integer>> result) { if (start >= num.length ) { ArrayList<Integer> item = convertArrayToList(num); result.add(item); } for (int j = start; j <= num.length-1; j++) { if (notcontainsDuplicate(num, start, j)) { swap(num, start, j); permuteUnique(num, start + 1, result); swap(num, start, j); } } }  private boolean notcontainsDuplicate(int[] arr, int start, int end) { for (int i = start; i <= end-1; i++) { if (arr[i] == arr[end]) { return false; } } return true; }

Also refer to http://www.cnblogs.com/TenosDoIt/p/3662644.html
Read full article from LeetCode - Permutations II | Darren's Blog