Java 全排列递归算法

无重复项的全排列

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> lists = new ArrayList<>();
    permulation(lists, nums, 0);
    return lists;
}

public void permulation(List<List<Integer>> lists, int[] nums, int start) {
    if (start == nums.length) {     // 当n定位到最后一个数时，即到递归出口
        List<Integer> list = new ArrayList<>();
        for(int num:nums){
            list.add(num);
        }
        lists.add(list);
        return;
    }
    for (int i = start; i < nums.length; i++) {
        swap(nums, start, i);   // 交换位置
        permulation(lists, nums, start + 1);
        swap(nums, start, i);   // 恢复原来的顺序，进行下一次交换
    }
}

public void swap(int[] nums,int i,int j){
    int temp=nums[i];
    nums[i]=nums[j];
    nums[j]=temp;
}

有重复项的全排列

将这个问题看作有 n 个排列成一行的空格，我们需要从左往右依次填入题目给定的 n 个数，每个数只能使用一次。

那么很直接的可以想到一种穷举的算法，即从左往右每一个位置都依此尝试填入一个数，看能不能填完这 n 个空格，在程序中我们可以用「回溯法」来模拟这个过程。

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    List<Integer> perm = new ArrayList<Integer>();
    boolean[] vis = new boolean[nums.length];
    Arrays.sort(nums);
    backtrack(nums, ans, vis, 0, perm);
    return ans;
}

public void backtrack(int[] nums, List<List<Integer>> ans, boolean[] vis, int idx, List<Integer> perm) {
    if (idx == nums.length) {
        ans.add(new ArrayList<Integer>(perm));
        return;
    }
    for (int i = 0; i < nums.length; ++i) {
        // 对原数组排序，保证相同的数字都相邻，然后每次填入的数一定是这个数所在重复数集合中「从左往右第一个未被填过的数字」，即如下的判断条件：
        if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
            continue;
        }
        perm.add(nums[i]);
        vis[i] = true;
        backtrack(nums, ans, vis, idx + 1, perm);
        vis[i] = false;
        perm.remove(idx);
    }
}