leetcode题目47. 全排列 II（java）

题目描述

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

示例

输入: [1,1,2]
输出:
 [
   [1,1,2],
   [1,2,1],
   [2,1,1]
 ]

代码

public List<List<Integer>> permuteUnique(int[] nums) {
    if (nums == null || nums.length <= 0) {
        return null;
    }
    Arrays.sort(nums);// 排序（升序或者降序都可以），排序是剪枝的前提
    boolean[] used = new boolean[nums.length];
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new LinkedList<>();
    backtrackII(nums, 0, used, path, result);
    return result;
}


public void backtrackII(int[] nums, int depth, boolean[] used, List<Integer> path, List<List<Integer>> result) {
    if (depth == nums.length) {
        // 所有数都填完了
        result.add(new ArrayList<Integer>(path));
        return;
    }
    // 注意，这里是从i = 0开始的
    for (int i = 0; i < nums.length; i++) {
        if(used[i]) {
            // 剪枝
            continue;
        }

        if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
            // 因题目要求不重复的全排列，所以如果当前的值和前一个值一样，则再次剪枝
            continue;
        }

        used[i] = true;
        path.add(nums[i]);
        backtrackII(nums, depth + 1, used, path, result);
        path.remove(path.size() - 1);
        // 撤销操作
        used[i] = false;
    }
}