47. 全排列 II

题意：

解题思路：

思路：回溯
1. 从前往后枚举每一位，每一次选择一个没有使用过的数字，然后将该数字置为已使用；
2. 然后将该数字加入数组中，递归下一层；
3. 递归终止返回时，将该数字改为“未被使用状态”，并从数组中移除该数字；
注意：if ($i > 0 && $nums[$i] == $nums[$i - 1] &&
            $this->visited[$i - 1] == 0) continue;
    -》剪枝，该元素与前一个元素相等，且前一个元素访问过，不使用，直接跳过

PHP代码实现：

class Solution {
    public $res = [];
    public $visited = [];
    function permuteUnique($nums) {
        sort($nums);
        $this->dfs([], $nums);
        return $this->res;
    }
    function dfs($array, $nums) {
        if (count($array) == count($nums)) {
            array_push($this->res, $array);
            return;
        }
        for ($i = 0; $i < count($nums); $i++) {
            // 第一次剪枝，去掉已经访问过的
            if (isset($this->visited[$i]) && $this->visited[$i] == 1) continue;
            // 第二次剪枝，该元素与前一个元素相等，且前一个元素访问过
            if ($i > 0 && $nums[$i] == $nums[$i - 1] && $this->visited[$i - 1] == 0) continue;
            $this->visited[$i] = 1;
            array_push($array, $nums[$i]);
            $this->dfs($array, $nums);
            array_pop($array);
            $this->visited[$i] = 0;
        }
    }
}

GO代码实现：

func permuteUnique(nums []int) [][]int {
    var pathNum []int
    var used = make([]bool, len(nums))
    var result [][]int
    sort.Ints(nums)
    dfs(nums, pathNum, used, &result)
    return result
}
func dfs(nums, pathNums []int, used []bool, result *[][]int) {
    if len(nums) == len(pathNums) {
        tmp := make([]int, len(nums))
        // 切片底层公用数据，所以要copy
        copy(tmp, pathNums)
        *result = append(*result, tmp)
        return
    }
    // 开始遍历原始数组的每个数字
    for i := 0; i < len(nums); i++ {
        if used[i] { continue }
        // 上一个元素与当前元素相同并且没有访问过
        if i != 0 && nums[i] == nums[i - 1] && !used[i - 1] {
            continue
        }
        used[i] = true
        pathNums = append(pathNums, nums[i])
        dfs(nums, pathNums, used, result)
        pathNums = pathNums[:len(pathNums)-1]
        used[i] = false
    }
}