力扣 46. 全排列 & 47. 全排列 II

46题目描述：

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

解析：

回溯法

Java:

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        backtrack(res, list, nums);
        return res;
    }
    public void backtrack(List<List<Integer>> res, List<Integer> list, int[] nums) {
        if(list.size() == nums.length) {
            res.add(new ArrayList<Integer>(list));
            return;
        }
        for(int i = 0; i < nums.length; i++) {
            if(!list.contains(nums[i])) {
                list.add(nums[i]);
                backtrack(res, list, nums);
                list.remove(list.size() - 1);
            }
        }
    }
}

JavaScript:

var permute = function(nums) {
    const res = [], path = [];
    backtracking(nums, nums.length, []);
    return res;
    
    function backtracking(n, k, used) {
        if(path.length === k) {
            res.push(Array.from(path));
            return;
        }
        for (let i = 0; i < k; i++ ) {
            if(used[i]) continue;
            path.push(n[i]);
            used[i] = true; // 同支
            backtracking(n, k, used);
            path.pop();
            used[i] = false;
        }
    }
};

47题目描述：

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

解析：

回溯法

Java:

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums == null || nums.length ==0) {
            return res;
        }
        int[] visited = new int[nums.length];
        Arrays.sort(nums);
        backTrack(res, nums, new ArrayList<Integer>(), visited);
        return res;
    }

    private void backTrack(List<List<Integer>> res, int[] nums, List<Integer> list, int[] visited) {
        if(list.size() == nums.length) {
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i = 0; i < nums.length; i++) {
            if(visited[i] == 1) {
                continue;
            }
            if(i > 0 && nums[i] == nums[i - 1] && visited[i - 1] == 0) {
                continue;
            }
            list.add(nums[i]);
            visited[i] = 1;
            backTrack(res, nums, list, visited);
            visited[i] = 0;
            list.remove(list.size() - 1);
        }
    }
}

JavaScript:

var permuteUnique = function(nums) {
    const res = [], list = [];
    if(nums == null || nums.length ==0) {
            return res;
        }
    nums = nums.sort((a, b) => a - b);
    dfs(nums, nums.length, []);
    return res;

    function dfs(n, k, visited) {
        if(list.length === k) {
            res.push(Array.from(list));
            return;
        }
        for(let i = 0; i < k; i++) {
            if(visited[i]) {
                continue;
            }
            if(i > 0 && nums[i] == nums[i - 1] && visited[i - 1] == 0) {
                continue;
            }
            list.push(n[i]);
            visited[i] = true;
            dfs(n, k, visited);
            list.pop();
            visited[i] = false;
        }
    }
};