全排列
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/permutations
解题思路
直接参考 回溯算法团灭排列/组合/子集问题
代码
class Solution {
public $res = [];
/**
* @param Integer[] $nums
* @return Integer[][]
*/
function permute($nums) {
$this->dfs([], $nums);
return $this->res;
}
function dfs($array, $candidates) {
if (count($array) === count($candidates)) {
$this->res[] = $array;
return;
}
for ($i = 0; $i < count($candidates); $i++) {
if (in_array($candidates[$i], $array)) continue;
$array[] = $candidates[$i];
$this->dfs($array, $candidates);
array_pop($array);
}
}
}
额外：LeetCode 47 全排列 Ⅱ，区别是 第一：加了一个sort，排序之后只有相邻元素才会相同 第二：判断去重条件，加了是否访问过的判断
class Solution {
public $res = [];
/**
* @param Integer[] $nums
* @return Integer[][]
*/
function permuteUnique($nums) {
sort($nums);
$this->dfs([], $nums, []);
return $this->res;
}
function dfs($array, $candidates, $visited) {
if (count($array) === count($candidates)) {
$this->res[] = $array;
return;
}
for ($i = 0; $i < count($candidates); $i++) {
if ($visited[$i]) continue;
if ($i > 0 && $candidates[$i] == $candidates[$i -1] && $visited[$i - 1]) continue;
$array[] = $candidates[$i];
$visited[$i] = 1;
$this->dfs($array, $candidates, $visited);
array_pop($array);
$visited[$i] = 0;
}
}
}
参考链接
