全排列 II

[louzhedong]

题目

出处：LeetCode 算法第47题

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

思路

相比于上一题，本题的元素是可以重复的，所以我们需要一个数组来保存当前的项是否已经添加了

解答

var permuteUnique = function (nums) {
  if (nums.length === 0) {
    return [];
  }
  var result = [];
  var resultStr = [];
  var used = [];
  var temp = [];
  DFS(nums, result, temp, used, resultStr);
  return result;
};

function copy(array) {
  var result = [];
  for (var i = 0, len = array.length; i < len; i++) {
    result.push(array[i]);
  }
  return result;
}

function DFS(nums, result, temp, used, resultStr) {
  if (temp.length === nums.length) {
    if (resultStr.indexOf(temp.join(',')) < 0) {
      result.push(copy(temp));
      resultStr.push(temp.join(','));
    }
  };
  for (var i = 0; i < nums.length; i++) {
    if (used[i]) {
      continue
    }
    if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
      continue
    }
    used[i] = true;
    temp.push(nums[i]);
    DFS(nums, result, temp, used, resultStr);
    used[i] = false;
    temp.pop();
  }
}