全排列「变题」

46. 全排列

开头先来一个小插曲，关于「排列」问题的总结可见 排列 / 组合 / 子集 问题

// 回溯
// 时间复杂度 : O(n * n!) -> n! 为叶子结点数量，每到叶子结点时就会 copy 一次 List，时间为 O(n)
// 空间复杂度 : O(n * n!) -> 回溯深度为 n，需要 O(n) 的栈空间；但存储答案的 List 需要 O(n * n!) 空间，两者取最大值
private boolean[] used;
private List<Integer> track = new ArrayList<>();
private List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
    used = new boolean[nums.length];
    f(nums);
    return ans;
}
private void f(int[] nums) {
    if (track.size() == nums.length) {
        ans.add(new ArrayList<>(track));
        return ;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        used[i] = true;
        track.add(nums[i]);
        f(nums);
        track.remove(track.size() - 1);
        used[i] = false;
    }
}

// 迭代
// 时间复杂度 : O(n * n!) -> n! 为叶子结点数量，每到叶子结点时就会 copy 一次 List，时间为 O(n)
// 空间复杂度 : O(n * n!) -> 临时的 List 和存储答案的 List
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> ans = new LinkedList<>();
    List<List<Integer>> temp = new LinkedList<>();
    ans.add(new LinkedList<>());
    for (int x : nums) {
        for (List<Integer> list : ans) {
            // 分别在 List 的 [0...n] 处插入当前元素
            for (int i = 0; i <= list.size(); i++) {
                // copy
                List<Integer> t = new LinkedList<>(list);
                // LinkedList 插入时不需要移动，但需要遍历查找到第 i 个位置
                t.add(i, x);
                temp.add(t);
            }
        }
        ans = new LinkedList<>(temp);
        temp = new LinkedList<>();
    }
    return ans;
}

变题一：全排列 (有重复)

题目详情可见 全排列 II

字符串版本题目可见 面试题 08.08. 有重复字符串的排列组合

private boolean[] used;
private List<Integer> track = new ArrayList<>();
private List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
    int n = nums.length;
    used = new boolean[n];
    // 注意要排序
    Arrays.sort(nums);
    f(nums);
    return ans;
}
private void f(int[] nums) {
    if (track.size() == nums.length) {
        ans.add(new ArrayList<>(track));
        return ;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
        used[i] = true;
        track.add(nums[i]);
        f(nums);
        used[i] = false;
        track.remove(track.size() - 1);
    }
}