递归 / 回溯--LeetCode 47. 全排列 II

47. 全排列 II

难度中等776
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：
输入：nums = [1,1,2] 输出： [[1,1,2], [1,2,1], [2,1,1]]
示例 2：
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

通过次数199,290
提交次数313,477

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function permuteUnique($nums) {
        $ret = [];
        if(!$nums) return $ret;
        sort($nums);//排序
        $this->permuteCore($nums, 0, $ret);
        return $ret;
    }
    // 回溯求解
    function permuteCore($nums, $begin, &$ret){
        $len = count($nums);
        if($begin >= $len){               // 到达最后一元素 打印该排列
            $res = [];
            foreach($nums as $num){
                $res[] = $num;
            }
            $ret[] = $res;
            return ;
        }
        for ($i = $begin; $i < $len; ++$i) {
            // 如果后续有重复数字 不需要交换
            if($i!=$begin && $nums[$i] == $nums[$begin]) continue;    
            $temp = $nums[$begin];// 交换首元素和i位置元素
            $nums[$begin] = $nums[$i];
            $nums[$i] = $temp;
            $this->permuteCore($nums, $begin+1, $ret);    // 递归到下一个元素
            //$temp = $nums[$begin];// 恢复交换前位置
            //$nums[$begin] = $nums[$i];
            //$nums[$i] = $temp;         
        }
    }
}