Leetcode 46. Full permutations of arrays

· TotalAccepted: 160245
· TotalSubmissions: 378230
· Difficulty: Medium
· Contributor: LeetCode
Given a collection of distinct numbers,return all possible permutations.
For example,
[1,2,3] have the following permutations:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
Method 1: Using backtracking method, first fix a character unchanged, and then arrange the characters after it; then replace the fixed characters with a character after it, and then find the full arrangement after it again.
For example, 123, first fix 1, find 23 Full Permutation (fix 2, find 3 full permutation; 2 and 3 exchange, fix 3, find 2 full permutation); 1 and 2 exchange, fix 2, find 13 Full Permutation (fix 1, find 3 full permutation...)...

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    perm(result,nums,0,nums.length-1);
    return result;
}
public static void perm(List<List<Integer>> result, int[] nums, int start, int end){
    if(start==end){
        Integer[] ele = new Integer[nums.length];
        for(int i=0; i<nums.length; i++){
            ele[i] = nums[i];
        }
        result.add(Arrays.asList(ele));
    }
    else{
        for(int i=start; i<=end; i++){
            int temp = nums[start];
            nums[start] = nums[i];
            nums[i] = temp;
            perm(result, nums,start+1,end);

            temp = nums[start];
            nums[start] = nums[i];
            nums[i] = temp;
        }
    }
}
}

There's another way to write it according to the idea of Law 1 (slightly less efficient, but helpful for understanding the next code question).

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        boolean[] used = new boolean[nums.length];
        perm(result,nums,list,used);
        return result;
    }
    public void perm(List<List<Integer>> res,int[] nums,List<Integer> list,boolean[] used){
        if(list.size() == nums.length){
            List<Integer> temp = new ArrayList<Integer>(list);
            res.add(temp);
        }
        else{
            for(int i = 0; i < nums.length; i++){
                if(used[i]) continue;
                used[i] = true;
                list.add(nums[i]);
                perm(res,nums,list,used);
                used[i] = false;
                list.remove(list.size()-1);
            }
        }
    }
}

Fa 2: It's similar to Fa 1, but I think it's better to understand than the first method. It can be called the insertion method. It also uses the idea of retrospective.
Take 123 as an example. First insert 1, then 2 can be inserted before 1 or after 1: 2 can be inserted before 1 (21), then 3 can be inserted in 3 places. First insert into the front to get 321, then remove 3, insert into the middle 231, remove 3, insert into the last 213, remove 3 and then trace back to the step of inserting 2, remove 2, insert 2 into the back of 1 to become 12, and then insert 2 into the back of 1. Insert 3 (also 3 cases 312, 132, 123)...

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        perm(result,nums,0,list);
        return result;
    }
    public void perm(List<List<Integer>> res,int[] nums,int end,List<Integer> list){
        if(end == nums.length){
            List<Integer> temp = new ArrayList<Integer>(list);
            res.add(temp);
        }
        else{
            for(int i = 0; i <= end; i++){
                list.add(i,nums[end]);
                perm(res,nums,end+1,list);
                list.remove(i);
            }
        }
    }
}

Leetcode 47. Full permutations of Permutations II arrays 2
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
In fact, the main idea is similar to the first method of the previous question, which is to fix one and then find the full arrangement after it. For the treatment of the same number, for example, 1, 1, 2, the whole arrangement of 1 and 12 has already been fixed, so the next one will not carry out the process of fixed and complete arrangement, but will continue directly and fix the next character. If the understander has any difficulty, he can see the second version of Item 1, which is revised on the basis of that version.

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        boolean[] used = new boolean[nums.length]; 
        Arrays.sort(nums);
        perm(nums,list,res,used);
        return res;
    }
    public void perm(int[] nums,List<Integer> list,List<List<Integer>> res,boolean[] used){
        if(list.size() == nums.length){
            res.add(new ArrayList<Integer>(list));
        }
        else{
            for(int i = 0; i < nums.length; i++){
                //Has been used
                if(used[i]) continue;
                //Like the previous one, and the former one is not used, the former one is not used now.
                //In fact, it means that it has been used in the last round.
                //So the same character as him should be used in the same round as the previous one, so continue directly.
                if(i > 0 && nums[i-1] == nums[i] && !used[i-1]) continue;
                used[i] = true;
                list.add(nums[i]);
                perm(nums,list,res,used);
                used[i] = false;
                list.remove(list.size() - 1);
            }
        }
    }
}