47.全排列 II

给定一个可包含重复数字的序列 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]]

提示:

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

思路

这道题目和排列问题的区别在与给定一个可包含重复数字的序列,要返回所有不重复的全排列。

这里又涉及到去重了。

求组合总和(三) ,求子集问题(二)我们分别详细讲解了组合问题和子集问题如何去重。

那么排列问题其实也是一样的套路。

还要强调的是去重一定要对元素经行排序,这样我们才方便通过相邻的节点来判断是否重复使用了。

我以示例中的 [1,1,2]为例 (为了方便举例,已经排序)抽象为一棵树,去重过程如图:

47.全排列 II

图中我们对同一树层,前一位(也就是nums[i-1])如果使用过,那么就进行去重。

一般来说:组合问题和排列问题是在树形结构的叶子节点上收集结果,而子集问题就是取树上所有节点的结果。

class Solution {
    List<List<Integer>> res=new ArrayList<>();
    List<Integer> path=new ArrayList<>();
    boolean[] used; 
    public List<List<Integer>> permuteUnique(int[] nums) {
        used=new boolean[nums.length];
        Arrays.sort(nums);
        process(nums);
        return res;
    }

    private void process(int[] nums){
      if(path.size()==nums.length){
          res.add(new ArrayList<>(path));
      }

      for(int i=0;i<nums.length;i++){
            // used[i - 1] == true,说明同⼀树⽀nums[i - 1]使⽤过
            // used[i - 1] == false,说明同⼀树层nums[i - 1]使⽤过
            // 如果同⼀树层nums[i - 1]使⽤过则直接跳过
          if(i>0&&nums[i-1]==nums[i]&&!used[i-1]){
              continue;
          }
          if(!used[i]){ //如果同⼀树⽀nums[i]没使⽤过开始处理
            used[i]=true;//标记同⼀树⽀nums[i]使⽤过,防止同一树支重复使用
            path.add(nums[i]);
            process(nums);
            //回溯,说明同⼀树层nums[i]使⽤过,防止下一树层重复
            path.remove(path.size()-1);
            used[i]=false;
          }
      }   
    }
}

  

  另一种解法

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {

        List<List<Integer>> ans=new ArrayList<>();
        List<Integer> numList=new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            numList.add(nums[i]);
        }
        List<Integer> path=new ArrayList<>();
        process(numList,path,ans);
        return ans;

    }

    private void process(List<Integer> numList,List<Integer> path,List<List<Integer>> ans){
        //base case
        if(numList.isEmpty()){
            ans.add(path);
            return;
        }

        HashSet<Integer> set=new HashSet<>();
        for(int i=0;i<numList.size();i++){
            if(!set.contains(numList.get(i))){
                set.add(numList.get(i));
             List<Integer> pickList=new ArrayList<>(path);
            pickList.add(numList.get(i));

            List<Integer> nextList=new ArrayList<>(numList);
            nextList.remove(i);
            process(nextList,pickList,ans);
            }
          

        }
    }
}

  

上一篇:剑指 Offer 47. 礼物的最大价值


下一篇:Noip模拟47 2021.8.25