题解 | #有重复项数字的所有排列#

方法一：递归算法

permutation(num, int start, int l) {
	if (start == l-1) {
    	print(num)
    	return;
    }
    for (int i = start + 1; i < l; i++) {
    	swap(num, start, i);
        permutation(num, i, l);
        swap(num, start, i);
    }
}

方法二： Permutation算法

1. 从num数组从右往左找出第一个满足条件num[i-1] < num[i]
2. 在i的右侧数组中num[i+1...l]，该数组满足递减性质，从该数组的右往左到i+1,找出第一个大于num[i-1]的数字num[index]
3. 交换num中index、i-1位置的数字，swap(num, index, i-1), 再将num[i...l]之间的数字进行反转
4. 重复1-3步骤，直到没有满足第一个条件的为止

import java.util.*;

public class Solution {
    void swap(int[] num, int i, int j) {
        int t = num[i];
        num[i] = num[j];
        num[j] = t;
    }

    void reverse(int[] num, int i, int j) {
        while (i < j) {
            swap(num, i, j);
            i++;
            j--;
        }
    }

    boolean next(int[] num) {
        for (int i = num.length - 1; i > 0; i--) {
            if (num[i] > num[i - 1]) {
                int index = i;
                // 从尾部往前到i+1，找出第一个大于num[i-1]的数
                for (int j = num.length - 1; j > i; j--) {
                    if (num[j] > num[i - 1]) {
                        index = j;
                        break;
                    }
                }
                swap(num, i - 1, index);
                reverse(num, i, num.length - 1);
                return true;
            }
        }
        return false;
    }

    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (num.length == 0) {
            return result;
        }
        Arrays.sort(num);
        do {
            ArrayList<Integer> r = new ArrayList<>();
            for (int j : num) {
                r.add(j);
            }
            result.add(r);
        } while (next(num));

        return result;
    }
}