没有重复项数字的全排列

public class Solution {

    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        boolean[] used = new boolean[num.length];
        ArrayList<Integer> currentPermute = new ArrayList<>();
        backtrack(num, res, currentPermute, used);
        return res;
    }

    public static void backtrack(int[] num,
                                 ArrayList<ArrayList<Integer>> res, ArrayList<Integer> currentPermute,
                                 boolean[] used) {
        int n = num.length;
        if (currentPermute.size() == n) res.add(new ArrayList<>(currentPermute));
        else {
            for (int i = 0; i < n; i++) {
                if (used[i]) continue;
                used[i] = true;
                currentPermute.add(num[i]);
                backtrack(num, res, currentPermute, used);
                used[i] = false;
                currentPermute.remove(currentPermute.size() - 1);
            }
        }
    }
}

public ArrayList<ArrayList<Integer>> permute (int[] num) {
        return permute1(num);
    }

    public ArrayList<ArrayList<Integer>> permute1 (int[] num) {
        ArrayList<ArrayList<Integer>> l = new ArrayList<>();
        ArrayList<Integer> ll = new ArrayList<>();
        for(int i=0;i<num.length;i++){
            ll.add(num[i]);
        }
        permute1_1(l,ll,0);
        return l;
    }

    public void permute1_1 (ArrayList<ArrayList<Integer>> l,ArrayList<Integer> ll,int pos) {
        if(pos == ll.size()){
            l.add(ll);
            return;
        }
        for(int i=pos;i<ll.size();i++){
            ArrayList<Integer> lt = new ArrayList<>(ll);
            int t = lt.get(i);
            lt.remove(i);
            lt.add(pos,t);
            permute1_1(l,lt,pos+1);
        }
    }

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型一维数组
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> permute (int[] num) {
        // write code here
        // 左程云老师讲过全排列的分支限界递归法解决不重复全排列问题
        // 调用一个递归函数，这个递归函数负责对当前i位置的数字进行与i ~ num.length - 1中的位置依次互换，然后继续考察i + 1处的情况

        // 算法的时间复杂度0(N!)，额外空间复杂度0(N!)

        // 用于记录所有路径的结果
        ArrayList<ArrayList<Integer>> finalResults = new ArrayList<>();

        // 调用这个递归函数，从num数组的0位置开始，将每一次找到的oneResult填进finalResult中
        process(num, finalResults, 0);

        // 返回最终的答案finalResults
        return finalResults;
    }

    public void process(int[] num, ArrayList<ArrayList<Integer>> finalResults, int i) {
        // 递归出口（底部）
        if (i == num.length) {
            // i越界了，说明整个数组遍历完毕了，将单个路径上的答案oneResult写入总答案finalResults中
            // 踩坑点1：这里一定要【现场新创建】一个ArrayList放入答案中，如果提前在主方法创建好，那么随着每次递归的调用，finalResults里面的值也会被修改
            ArrayList<Integer> oneResult = new ArrayList<>();
            for (Integer n : num) {
                oneResult.add(n);
            }
            finalResults.add(oneResult);
        }

        // 递归分支
        for (int j = i; j < num.length; j++) {
            // 将num[j]算入这次的结果中
            swap(num, i, j);
            // 在算入num[j]的基础上继续考察num数组中i+1往后的位置
            process(num, finalResults, i + 1);
            // 注意！恢复现场，继续尝试将将num[j+1]算入这次的结果中
            // 踩坑点2：一定要【恢复现场】，要不然无法准确列出要分支的情况
            swap(num, j, i);
        }
    }

    // 数组元素交换函数
    public void swap(int[] num, int i, int j) {
        if (i == j) {
            return;
        }
        int t = num[i];
        num[i] = num[j];
        num[j] = t;
    }
}

ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();

public ArrayList<ArrayList<Integer>> permute (int[] num) {
    // write code here
    Arrays.sort(num);
    recur(num ,new boolean[num.length] ,new ArrayList<>());
    return res;
}

public void recur(int[] num ,boolean[] flag ,ArrayList<Integer> list){
    if(list.size()==num.length){
        res.add(new ArrayList<>(list));
        return;
    }
    for(int i=0;i<num.length;i++){
        if((i>0 && num[i]==num[i-1] && !flag[i]) || flag[i]){
            continue;
        }
        list.add(num[i]);
        flag[i]=true;
        recur(num ,flag ,list);
        flag[i]=false;
        list.remove(list.size()-1);
    }
}

public ArrayList<ArrayList<Integer>> permute (int[] num) {
        ArrayList<ArrayList<Integer>> ans=new ArrayList<>();
        ArrayList<Integer> list=new ArrayList<>();
        build(num,ans,list);
        return ans;
    }
    public void build(int[] num,ArrayList<ArrayList<Integer>> ans,ArrayList<Integer> list){
        if(list.size()==num.length){  //截至条件（终止条件）
            ans.add(new ArrayList<>(list));
        }
        for(int i=0;i<num.length;i++){
            if(list.contains(num[i])){    //因为这个题没有重复的数字，   所以当list中已经有了这个数字，那就剪枝
                continue;
            }
            list.add(num[i]);
            build(num,ans,list);
            list.remove(list.size()-1);
        }
    }

import java.util.*;

import java.util.stream.Collectors;

public class Solution {

    private ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>();
    private ArrayList<Integer> current = new ArrayList<Integer>();

    public ArrayList<ArrayList<Integer>> permute(int[] num) {

        int max = getMax(num);
        int[] numCount = new int[max + 1];
        for (int idx = 0; idx < num.length; idx++) {
            numCount[num[idx]]++;
        }
        dfs(num, numCount, num.length);
        Set<ArrayList<Integer>> set = new HashSet<ArrayList<Integer>>(this.all);
        this.all.clear();
        this.all.addAll(set);
        Collections.sort(this.all, new Comparator<ArrayList<Integer>>() {
            public int compare(ArrayList<Integer> self, ArrayList<Integer> other) {
                int min = Math.min(self.size(), other.size());
                for (int idx = 0; idx < min; idx++) {
                    if (self.get(idx) != other.get(idx)) {
                        return self.get(idx).compareTo(other.get(idx));
                    }
                }
                if (self.size() > other.size()) {
                    return self.get(min + 1);
                } else if (self.size() < other.size()) {
                    return other.get(min + 1);
                }
                return 0;
            }
        });
        return this.all;
    }

    public void dfs(int[] num, int[] numCount, int n) {
        if (this.current.size() == n) {
            this.all.add((ArrayList<Integer>)this.current.clone());
            return;
        }
        for (int idx = 0; idx < n; idx++) {
            int count = getCount(this.current, num[idx]);
            if (count < numCount[num[idx]]) {
                this.current.add(num[idx]);
                dfs(num, numCount, n);
                this.current.remove(this.current.size() - 1);
            }
        }
    }

    public static int getCount(ArrayList<Integer> list, int num) {
        long count = list.stream().filter(item->item == num).collect(
                         Collectors.counting());
        return Long.valueOf(count).intValue();
    }

    public static int getMax(int[] num) {
        int max = Integer.MIN_VALUE;
        for (int idx = 0; idx < num.length; idx++) {
            if (max < num[idx]) {
                max = num[idx];
            }
        }
        return max;
    }
}

import java.util.*;
## 经典回溯
public class Solution {
    List<Integer> list = new ArrayList<>();
    ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        Arrays.sort(num);
        dfs(num,list);
        return result;
    }

    private void dfs(int[] num,List<Integer> list){
        if(list.size() == num.length){
            result.add(new ArrayList<>(list));
            return;
        }
        for(int i = 0; i < num.length; i ++){
            if(list.contains(num[i])){
                continue;
            }
            list.add(num[i]);
            dfs(num,list);

            list.remove(list.size() - 1);
        }

    }
}

import java.util.*;

public class Solution {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<Integer> list = new ArrayList<>();
        backTrack(num, list);
        return res;
    }

    public  void backTrack(int[] num, ArrayList<Integer> list) {
        if (list.size() == num.length) {
            res.add(new ArrayList<>(list));
            return;
        }

        for (int i = 0; i < num.length; i++) {
            if (list.contains(num[i]))
                continue;

            list.add(num[i]);
            backTrack(num, list);
            list.remove(list.size() - 1);
        }
    }
}

import java.util.*;

public class Solution {

    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        boolean[] isUsed = new boolean[num.length];
        ArrayList<Integer> list = new ArrayList<>();
        Arrays.sort(num);

        dfs(num, isUsed, list);

        return res;
    }

    public void dfs(int[] num, boolean[] isUsed, ArrayList<Integer> list) {
        if (list.size() == num.length) {
            res.add(new ArrayList(list));
        }

        for (int i = 0; i < num.length; i ++) {
            if (isUsed[i] == true) continue;
            if (i > 1 && num[i] == num[i - 1]) continue;
            list.add(num[i]);
            isUsed[i] = true;
            dfs(num, isUsed, list);
            isUsed[i] = false;
            list.remove(list.size() - 1);
        }
    }
}

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> list=new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> path=new ArrayList<Integer>();
        dfs(num,path,list);
        return list;
    }
    public void dfs(int[] nums,ArrayList<Integer> path,ArrayList<ArrayList<Integer>> list){
        if(path.size()==nums.length){
            list.add(new ArrayList<Integer>(path));
            return;
        }
        for(int i=0;i<=nums.length-1;i++){
            if(path.contains(nums[i])){continue;}
            path.add(nums[i]);
            dfs(nums,path,list);
            path.remove(path.size()-1);
        }
    }
}

import java.util.*;
public class Solution {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    ArrayList<Integer> track = new ArrayList<>();
    
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        backtrack(num);
        return res;
    }
    
    public void backtrack(int[] num){
        if(track.size()==num.length) {
            res.add(new ArrayList<Integer>(track));
            return;
        }
        
        for(int i : num){
            if(track.contains(i)) continue;
            track.add(i);
            backtrack(num);
            track.remove(track.size()-1);
        }
        return;
    }
}

public class Solution {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
    int len;
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        if(num==null||num.length==0) return ans;
        //先对数组排序保证最后返回的结果是按字典排序输出
        Arrays.sort(num);
        len = num.length;
        //创建一个数组记录已经加入数组的元素
        boolean[] isVisi = new boolean[len];
        //递归添加元素
        dfs(num,isVisi,new ArrayList());
        return ans;
    }
    void dfs(int[] num,boolean[] vis,ArrayList<Integer> ls){
        if(ls.size()==len){
            ans.add(new ArrayList(ls));
            return;
        }
        for(int i = 0;i<len;i++){
            if(vis[i]) continue;
            vis[i] = true;
            ls.add(num[i]);
            dfs(num,vis,ls);
            //回溯
            vis[i] = false;
            ls.remove(ls.size()-1);
        }
    }
}

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        Arrays.sort(num); 
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if(num.length == 0){
            return res;
        }
        ArrayList<Integer> list = new ArrayList<>();
        //数组转list集合（重点！！！）
        for(int n : num){
            list.add(n);
        }
        recursion(res, list, 0);
        return res;
    }
    
    int temp = 0;
    public void swap(ArrayList<Integer> list, int i1, int i2){
        temp = list.get(i1);
        list.set(i1, list.get(i2));
        list.set(i2, temp);
    }
    
    public void recursion(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> list, int index){
        if(index == list.size() - 1){
            res.add(new ArrayList<>(list));//官方答案这里写错了，不new的话，存的内存地址就是同一个，那么就会相同结果
        }else{
            for(int i = index; i < list.size(); i++){
                swap(list, i, index);//递归
                recursion(res, list, index + 1);
                swap(list, i, index);//回溯
            }
        }
    }
}

import java.util.*;

public class Solution {
    public void swap(ArrayList<Integer> nums, int i, int j) {
        if (i == j) {
            return;
        }
        int temp = nums.get(i);
        nums.set(i, nums.get(j));
        nums.set(j, temp);
    }

    public void recursive(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> nums, int startIndex) {
        if (startIndex == nums.size() - 1) {
            result.add(new ArrayList<>(nums));
            return;
        }
        for (int i = startIndex; i < nums.size(); i++) {
            swap(nums, startIndex, i);
            recursive(result, nums, startIndex + 1);
            swap(nums, startIndex, i);
        }
    }

    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<Integer> nums = new ArrayList<>();
        for (int n : num) {
            nums.add(n);
        }
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        recursive(result, nums, 0);
        return result;
    }
}