Lexi's Leetcode solutions

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

Posted on: August 8, 2013

平时的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;
    }
  }
}
Advertisements

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

这个解释how to avoid replicate很棒,不过实现上,yu’s coding更简洁些。

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: