全排列Ⅱ java实现（回溯算法，有实现思路、带注释）

全排列Ⅱ完整实现过程

• 问题详情（Derived from LeetCode）
  
• 问题分析及思路

本题在全排列的基础上对结果限定了条件（不可重复），所以我们首先对全排列的所有结果举例开来（利用深度优先搜索的方法，进行递归操作），然后再用List集合的contains方法对得出的结果进行是否重复的判断，来得出我们最终的结果。

问题树结构化，每一棵树与剩下没匹配的数进行排列，直到都匹配完成

• 下面为代码实现过程

package LanQiao;
import java.util.*;
public class Permutation{
    static int size;
    public static void main(String[] args) {
    	int nums[] = {1,1,2};
        List<List<Integer>> res = new ArrayList<List<Integer>>(); //存储最终结果
        size = nums.length; //数组长度
        Deque<Integer> path = new ArrayDeque<Integer>();  //充当栈结构，方便回溯上一步操作
        boolean[] visit = new boolean[size];    //visit数组记录当前元素是否已经被访问
        int deepth = 0;  //树的深度
        dfs(nums,path,visit,deepth,res);
        System.out.println(res.toString());
    }
    static void dfs(int[] nums,Deque<Integer> path,boolean[] visit,int deepth,List<List<Integer>> res) {
        if(deepth == size){ //当数的深度达到的数组的长度，说明数组的所有元素已经被访问，完整序列构造完成
            List<Integer> list = new ArrayList<Integer>(path);
            if(res.contains(list) == false)
            res.add(list);
        }else{
            for(int i = 0; i < size; i++){
                if(visit[i]){
                    continue;
                }
                path.addLast(nums[i]);  //入栈
                visit[i] = true;   //当前元素已被访问，赋值true
                dfs(nums,path,visit,deepth+1,res);
                path.removeLast();  //出栈
                visit[i] = false;  //回溯上一步操作，将上一步元素的访问状态设为false
            }
        }
    }
}

关键代码解析

1. 状态变量。boolean visit[size]数组，用来表明里面元素的访问状态，false表明没有被访问（使用），true代表已经被访问。当visit[i]为false时我们将对应下标元素入栈，入栈后再将该元素的布尔值设定为true，当进入下一次递归时，就不会重复入栈。
2. 栈结构(path)。回溯算法的实现当然少不了栈结构，主要为了返回上一步的操作，例如1，1，2排列完成就要返回到1，2这棵树，其中回溯了两步，大家可以根据上面的树结构进行演示一遍。代码中我们使用了ArrayDeque类而没有使用Stack的原因是ArrayDeque类实现了Collection接口，既可以实现栈的结构特性，而且它可以不用手动去逆序存储到ArrayList类中，ArrayList的一种构造方法（ArrayList(Collection<? extends E> c) ）就可以按逆序存储到ArrayList集合中。
3. 去重复操作。if(res.contains(list) == false) res.add(list);
   这段代码是判断当前list集合是否与res里面的集合重复，如果不重复则添加进去。

感谢您的观看，如果我的这篇博客对你有所帮助，欢迎留言点赞收藏哦！😉😃