回溯算法解决全排列

回溯法

采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：

46. 全排列

难度中等1542收藏分享切换为英文接收动态反馈

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>>  res=new LinkedList<>();
        int len=nums.length;
        if(len==0)
        return res;
        Deque<Integer>  path=new ArrayDeque<>();
        boolean []used=new boolean[len];
        int depth=0;
        dfs(nums,len,0,used,res,path);
        return  res;


    }
    private  void dfs(int []nums,int len,int depth,boolean[] used,List<List<Integer>> res,Deque<Integer> path)
    {
        if(depth==len){
            res.add(new LinkedList<>(path));//这里不能写res.add(path);
            return;
        }
        for(int i=0;i<len;i++){
//判断元素是否被取到
            if(!used[i]){
                used[i]=true;
                path.addLast(nums[i]);
                dfs(nums,len,depth+1,used,res,path);
//撤销前面所做的选择
                used[i]=false;
                path.removeLast();
            }
        }
    }
    }

 该段代码的执行过程

{进入递归

i=0

used[true,false,false];

path[1]

   {进入递归

   i=1;

used[t,t,f];

path[1,2];

       {进入递归

        i=2;

        used[t,t,t];

        path[1,2,3];

                 {进入递归

                     return

                 }

          used[t,t,f]

         path[1,2]

        }

   used[t,f,f]

   path[1]

     i=2

    used[t,f,t]

     path[1,3]

        {进入递归

       used[t,t,t];

       path[1,3,2]

        }

   }

}

只是一部分过程，表示的不清楚，建议去debug

47. 全排列 II

难度中等798收藏分享切换为英文接收动态反馈

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

只需要在上面代码做出一点改进，现将nums数组排序 

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>>  res=new LinkedList<>();
    int len=nums.length;
    if(len==0){
        return  res;
    }
    Deque<Integer>  path=new ArrayDeque<>();
    boolean []used=new boolean[len];
    Arrays.sort(nums);
    int depth=0;
    dfs(nums,len,0,used,res,path);
    return  res;

    }
    private void dfs(int []nums,int len,int depth, boolean []used,List<List<Integer>>  res, Deque<Integer>  path){
 if(depth==len){
     res.add(new ArrayList<>(path));
     return;
 }
 for(int i=0;i<len;i++){
     if(!used[i]){
           //i必须大于0，这个取得元素不能和上一个相同，上一个元素一定被使用过
           //used[i-1]==false这个条件要好好思考，used[i-1]==true也同样成立
         if(i>0 &&nums[i]==nums[i-1] && used[i-1]==false){
             continue;
         }
         path.add(nums[i]);
         used[i]=true;
         dfs(nums,len,depth+1,used,res,path);
         used[i]=false;
         path.removeLast();
     }
 }
    }
}