<?php


class Solution {

    public $result = [];
    public $vis = [];
    /**
     * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function permuteUnique($nums) {

        sort($nums);

        $this->backTrack($nums, 0, []);

        return $this->result;
    }


    function backTrack($nums, $step, $path) {

        if($step === count($nums)){

            $this->result[] = $path;

            return;
        }

        for ($i = 0; $i < count($nums); $i++){

            if($this->vis[$i] || ($i > 0 && $nums[$i] === $nums[$i - 1] && !$this->vis[$i - 1]))
                continue;


            $path[] = $nums[$i];

            $this->vis[$i] = true;

            $this->backTrack($nums, $step + 1, $path);

            $this->vis[$i] = false;

            array_pop($path);

        }


    }


}