[LC] 0047 Permutations II

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/permutations-ii/">Permutations II</a>
 * 数组；回溯；排序
 */
class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];

        Arrays.sort(nums);
        backtrack(0, nums, path, visited, res);
        return res;
    }

    private void backtrack(int cur, int[] nums, List<Integer> path, boolean[] visited, List<List<Integer>> res) {
        if (cur == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (visited[i] || (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])) {
                continue;
            }
            visited[i] = true;
            path.add(nums[i]);
            backtrack(cur + 1, nums, path, visited, res);
            path.remove(path.size() - 1);
            visited[i] = false;
        }
    }
}

Go

import "sort"

func permuteUnique(nums []int) (res [][]int) {
    var path []int
    n := len(nums)
    visited := make([]bool, n)

    var backtrack func(int)
    backtrack = func(cur int) {
        if cur == n {
            res = append(res, append([]int{}, path...))
            return
        }

        for i := 0; i < n; i++ {
            if visited[i] || (i > 0 && nums[i] == nums[i-1] && !visited[i-1]) {
                continue
            }
            visited[i] = true
            path = append(path, nums[i])
            backtrack(cur + 1)
            path = path[:len(path)-1]
            visited[i] = false
        }
    }

    sort.Ints(nums)
    backtrack(0)
    return res
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
    let res = [];
    let path = [];
    const n = nums.length;
    let visited = new Array(n).fill(false);

    const backtrack = (cur) => {
        if (cur === n) {
            res.push([...path]);
            return;
        }

        for (let i = 0; i < n; i++) {
            if (visited[i] || (i > 0 && nums[i] === nums[i - 1] && !visited[i - 1])) {
                continue;
            }
            visited[i] = true;
            path.push(nums[i]);
            backtrack(cur + 1);
            path.pop();
            visited[i] = false;
        }
    }

    nums.sort((a, b) => a - b);
    backtrack(0);
    return res;
};

PHP

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function permuteUnique(array $nums): array {
        $res = [];
        $path = [];
        $n = count($nums);
        $visited = array_fill(0, $n, false);

        sort($nums);
        $this->backtrack(0, $nums, $path, $visited, $res);
        return $res;
    }

    private function backtrack($cur, $nums, $path, $visited, &$res): void {
        $n = count($nums);
        if ($cur === $n) {
            $res[] = $path;
            return;
        }

        for ($i = 0; $i < $n; $i++) {
            if ($visited[$i] || ($i > 0 && $nums[$i] === $nums[$i - 1] && !$visited[$i - 1])) {
                continue;
            }
            $visited[$i] = true;
            $path[] = $nums[$i];
            $this->backtrack($cur + 1, $nums, $path, $visited, $res);
            array_pop($path);
            $visited[$i] = false;
        }
    }
}