全排列

[louzhedong]

题目

出处：LeetCode 算法第46题

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

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

思路

类似的这种问题只能通过递归遍历的方式来获得所有可能的情况。与前面的组合总和的思路是一样的。

解答

var permute = function (nums) {
  if (nums.length === 0) {
    return [];
  }
  var result = [];
  var temp = [];
  DFS(nums, 0, result, temp);
  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, level, result, temp) {
  if (temp.length === nums.length) {
    result.push(copy(temp));
  };
  for (var i = 0; i < nums.length; i ++) {
    if (temp.indexOf(nums[i]) < 0) {
      temp.push(nums[i]);
      DFS(nums, i, result, temp);
      temp.pop(nums[i]);
    }
  }
}