全排列

递归不支持字典序,只支持全排列

1. 不含重复元素的全排列

/**
     * <p>
     * 求数组 a 从 a[start] 到 a[end] 的全排列
     * 每次选中一个元素放在位置为 start 上，然后递归排列 a[start+1] a[end]
     * 支持字典序（要求初始序列为字典序）
     * 不支持重复元素
     */
    public void recur2(int[] a, int start, int end) {
        if (start == end) {
            count2++;
            System.out.println(Arrays.toString(a));
            return;
        }
        for (int i = start; i <= end; i++) {
            swap(a, i, start);
            recur2(a, start + 1, end); // 递归排列
            swap(a, i, start);
        }
    }

2. 含重复元素

  public void recur3(int[] a, int start, int end) {
        if (start == end) {
            count3++;
            System.out.println(Arrays.toString(a));
            return;
        }
        HashSet<Integer> set = new HashSet<>();
        for (int i = start; i <= end; i++) {
            if (set.contains(a[i])) {
                // 已经交换过值等于 a[i] 到 a[left] 的元素不再重复交换
                continue;
            }
            set.add(a[i]); // 记录[start...right]中已经交换到a[left] 的元素
            swap(a, i, start);
            recur3(a, start + 1, end);
            swap(a, i, start);
        }
    }

非递归处理

• 支持处理重复元素（不包含重复结果）
• 返回结果为字典序

  public List<List<Integer>> permuteUnique2(int[] a) {
        Arrays.sort(a);
        List<List<Integer>> res = new ArrayList<>();
        if (a == null || a.length == 0) return res;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < a.length; i++) list.add(a[i]);
        res.add(list);

        int j = a.length - 1;
        while (true) {
            j = a.length - 2;
            while (j >= 0 && a[j] >= a[j + 1]) j--;
            // 从右往左找到第一个a[j]< a[j+1]
            if (j == -1) { // 说明当前a[] 顺序为降序, 全排列结束
                break;
            }
            // 从[j+1,) 往后找大于 a[j]的最小值，与a[j] 交换
            int minIndex = j + 1;
            for (int k = minIndex + 1; k < a.length; k++) {
                if (a[k] > a[j] && a[k] <= a[minIndex]) {
                    // = 必须要取，保证目标值有多个时，与 a[j] 交换的是最后一个值,使得交换后[j+1, ) 之后的数字仍然保持降序
                    minIndex = k;
                }
            }
            swap(a, minIndex, j);

            // [end,之后的所有元素是逆序，反转即可
            reverse(a, j + 1, a.length - 1);
            list = new ArrayList<>();
            for (int i = 0; i < a.length; i++) list.add(a[i]);
            res.add(list);
        }
        return res;
    }

    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }