Leetcode: Permutations II

Permutations II

My Submissions

Total Accepted: 58417 Total Submissions: 216886 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,1,2], [1,2,1], and [2,1,1].

Subscribe to see which companies asked this question

Hide Tags

 Backtracking

Show Similar Problems

-------------------------------------------------------------------------------------

BT.
Same as Permutations I. 
Note: 

vector<int>::iterator it = vt.begin();
vt.insert(it, nums[i]);
//insert a val before 'it'! In the end, it=vt.end(), (it)[0] will be wrong!!

SO use following:
vector<int>::iterator pre = it - 1;
vt.insert(pre, nums[i]);

////////////////////////////////////////////////////////////////////////

class Solution {

 public:

        void backTrac(vector<int>& nums, vector<vector<int>> &result, vector<vector<int>> &tmp, int i){

               if (i <= 0){ //when nums.size()==1

                      vector<vector<int>> tmp1;

                      vector<int> vTmp;

                      vTmp.push_back(nums[i]);

                      tmp1.push_back(vTmp);

                      tmp = tmp1;

                      result = tmp;//when nums.size()==1

                      return;

               }

               else{

                      backTrac(nums, result, tmp, i - 1);

                      //insertion

                      vector<vector<int>> tmp1;

                      for (int m = 0; m<tmp.size(); m++){

                            for (int n = 0; n <= tmp[m].size(); n++){

                                   vector<int> vt;

                                   vt = tmp[m];

                                   vector<int>::iterator it = vt.begin();

                                   it = it + n;

                                   if (i == nums.size()) break;

                                   //vt.insert(it, nums[i]);

                                   if (n == 0) vt.insert(it, nums[i]);

                                   else {

                                          vector<int>::iterator pre = it - 1;

                                          if (((pre)[0]) != nums[i])vt.insert(it, nums[i]); //insert a val before it! In the end, it=vt.end(), (it)[0] will be wrong!!

                                          else break;

                                   }

                                   tmp1.push_back(vt);

                            }

                      }

                      tmp = tmp1;

                      result = tmp;

               }

        }

        vector<vector<int>> permuteUnique(vector<int>& nums) {

               vector<vector<int>> result, tmp;

               if (nums.size() == 0)return result;

               int i = nums.size() - 1;

               backTrac(nums, result, tmp, i);

               return result;

        }

 };