[leetcode] Permutations II | 一个带dup的array的所有unique permutation

Posted by: lexigrey on: August 8, 2013

• In: leetcode
• 1 Comment

平时的permutation有一个boolean used[]，如果arr[i]在之前的layer里用过了，就不能再用了。比如{1, 2, 1}，到pos2的时候，看即使arr[2]是“1”，但是这个1不是第一个用过的1，所以还可以放在当前pos当中。但是在pos0的时候，如果想用第二个1，就不行了（当前pos已经有人用过数字1了，即使用的是arr[0]不是当前想用的arr[2]，但是是同一个数字就不行），所以skip掉。因此，算法是“在每个position存一个hashset记录在这个position放过那些数字，若是以前放过了，这次就别放了。“

public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
  ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    if (num.length == 0)
  return result;
  permute(num, 0, new int[num.length], new boolean[num.length], result);
  return result;
}
private void permute(int[] num, int pos, int[] path, boolean[] used, ArrayList<ArrayList<Integer>> result) {
  if (pos == path.length) {
    result.add(convertToIntegerList(path));
    return;
  }
  Set<Integer> layerTried = new HashSet<Integer>();
  for (int i = 0; i < num.length; i++) {
    if (!layerTried.contains(num[i]) && used[i] == false) {
      path[pos] = num[i];
      used[i] = true;
      permute(num, pos + 1, path, used, result);
      layerTried.add(num[i]);
      used[i] = false;
    }
  }
}

Tags: dfs, duplicate, subsets/permutation, 固定解法