spring自定义注解

47. 全排列 II

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

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

示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

通过次数115,255

提交次数185,765

题解

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        traceBack(nums, new LinkedList<Integer>(), used,res);
        return res;
    }
    void traceBack(int[] nums, LinkedList<Integer> temp, boolean[] used, List<List<Integer>> res){
        if( temp.size() == nums.length){
            res.add(new LinkedList<>(temp));
            return;
        }
        for(int i =0; i < nums.length; i++){
            //used[i] == true 被选择的过的数不用再放进去了
            //接下来，如果当前节点和他之前的节点一样， 并且他的前一个节点已经被遍历过了， 也不需要了
            if( used[i] == true || ( i > 0 && nums[i] == nums[i-1] && !used[i-1])){
                continue;
            }
            temp.add(nums[i]);
            used[i] = true;
            traceBack( nums, temp, used , res);
            temp.pollLast();
            used[i] = false;
        }
    }
}

加上(i>0 && nums[i]==nums[i-1] && !used[i-1])，注意：若used[i-1]==false表示在同一层前一个相同的数已被访问过然后又被撤销（撤销就是used[i]又被置为false）。实际上这里判断写!used[i-1]或者used[i-1]都可以，!used[i-1]是回溯树同一层剪枝（水平），used[i-1]是回溯数同一条剪枝（竖直），但是同一层剪枝效率更高。

基本框架

LinkedList result = new LinkedList();
public void backtrack(路径，选择列表){
    if(满足结束条件){
        result.add(结果);
    }
    for(选择：选择列表){
        做出选择;
        backtrack(路径，选择列表);
        撤销选择;
    }
}

全排列，没有重复

class Solution {
    //回溯算法:不合适就退回上一步

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> list = new ArrayList<>(); //全局list用于存储最后的全排列结果
        int len = nums.length;

        //特判
        if(len==0)  return list;
        boolean[] used = new boolean[len]; //默认全为false，表示节点是否访问过（是：true,否：false)

        List<Integer> path = new ArrayList<>();//存储全排列路径
        dfs(nums,0,len,used,path,list);

        return list;

    }
    public void dfs(int[] nums, int depth, int len, boolean[] used,List<Integer> path, List<List<Integer>> list){ //depth用来表示当前的状态在第几层，当depth==len表示一条完整的排列已经找到了
        if(depth==len){
            list.add(new ArrayList<Integer>(path));
            return;
        }
        // 在非叶子结点处产生不同的分支，这一操作的语义是：在还未选择的数中依次选择一个元素作为下一个位置的元素，通过一个循环实现
        for(int i=0; i<len; i++){
            if(used[i]) continue;

            path.add(nums[i]);
            used[i] = true;

            dfs(nums,depth+1,len,used,path,list);
            // 注意：下面这两行代码发生「回溯」，回溯发生在从 深层结点 回到 浅层结点 的过程，代码在形式上和递归之前是对称的
            used[i] = false;
            path.remove(path.size()-1);

        }
    }
}

作者：cherry-n1
链接：https://leetcode-cn.com/problems/permutations-ii/solution/quan-pai-lie-i-quan-pai-lie-ii-hui-su-fa-javadai-m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 mym_74@163.com