2020-09-18-PHP 回溯算法求解全排列

layout: posttitle: PHP 回溯算法求解全排列
subtitle: PHP 回溯算法求解全排列
date: 2020-09-18
author: he xiaodong
header-img: img/default-post-bg.jpg
catalog: true
tags:
- Go
- PHP
- LeetCode 46 47
- 回溯算法
- 全排列

全排列

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

示例:

输入: [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;
        }
    }
}

参考链接

1. 回溯算法团灭排列/组合/子集问题

最后恰饭 阿里云全系列产品/短信包特惠购买 中小企业上云最佳选择 阿里云内部优惠券