Leetcode 47. Permutations II-白红宇

Leetcode 47. Permutations II

阅读量：4697 次

发布时间：2019-06-09

本文共 1090 字，大约阅读时间需要 3 分钟。

47. Permutations II

Total Accepted: 80610

Total Submissions: 277081

Difficulty: Medium

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,

[1,1,2] have the following unique permutations:

[  [1,2,3],  [1,3,2],  [2,1,3],  [2,3,1],  [3,1,2],  [3,2,1]]

思路：回溯法，和类似，但是本题的元素是可以有重复的，所以处理上有所不同。具体做法是先排序，然后0到nums.size()-1的位置上，每个位置放入当前剩下元素的每个类别。

例如对于[1,2,1]，排序后为[1,1,2]，有2类数。

第一次递归形成[1]（下次递归还有2类数）和[2]（下次递归只有1类数）；

第二次递归形成[1,1]（下次递归还有1类数） [1,2]（下次递归还有1类数）和[2,1]（下次递归还有1类数）；

第三次递归形成[1,1,2] [1,2,1] [2,1,1]

代码：

1 class Solution { 2 public: 3     void permuteUnique(vector
        
         
           > &res,vector
          
            nums,vector
           
             v,int cur){ 4         if(!nums.size()){ 5             res.push_back(v); 6             return; 7         } 8         //每个位置，每个种类的数只能放一次 9         for(int i=0;i

> permuteUnique(vector

& nums) {20 vector

> res;21 vector

v;22 sort(nums.begin(),nums.end());23 permuteUnique(res,nums,v,0);24 return res;25 }26 };