[LeetCode 46/47]PHP 回溯算法求解全排列

码农天地 - 2020-09-20 10:20:52

原文链接: 何晓东博客

全排列

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

示例:


输入: [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/probl...

解题思路

直接参考回溯算法团灭排列/组合/子集问题

代码


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;

         }

     }

}

参考链接

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

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

特别申明：本文内容来源网络，版权归原作者所有，如有侵权请立即与我们联系（cy198701067573@163.com），我们将及时处理。