LeeCode problems

unique_permutations.cpp

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

void printVector(vector<int> & data)
{ 
  cout << "[";
  for (int j = 0; j < data.size(); j++)
    {
      if (j != data.size() - 1 )
        cout << data[j] << ", ";
      else
        cout << data[j] << "]\n";
    }
}

void printPermutations(vector<vector <int>> & data)
{
  for ( int i = 0; i < data.size(); i++)
    {
      printVector(data[i]); 
    }  
}

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

  // this will never be called in recursion, more to handle special case; 
  if (nums.size() == 0 ) return(result); 

  // if there is only one element, this case deals with it; 
  if (nums.size() == 1 )
    {
      result.push_back(nums);
      return(result);
    }

  // when there are two or more elements
  // construct a vector which is a subvector of nums, without nums[0]; 
  vector<int> rest(nums.begin() + 1, nums.end());

  // find all the unique permutation of that vector
  vector<vector<int>> tmpResult = permuteUnique(rest);

  // add nums[0] to all the possible locations of each vector returned
  // in the tmpResult, only if is passed uniqueness checking;
  for (int i = 0; i < tmpResult.size(); i++)
    {
      for (int j = 0; j<=tmpResult[i].size(); j++)
        {
          vector<int> item = tmpResult[i];
          item.insert(item.begin() + j, nums[0]);
          if (find(result.begin(), result.end(), item) == result.end())
            {
              result.push_back(item); 
            }
        }
    }
  return(result); 
}

int main()
{
  vector<int> a = {1, 2, 3};
  vector<vector<int>> ret = permuteUnique(a);
  cout << "Finding unique permutations for "; printVector(a); 
  printPermutations(ret);
  
  a = {1, 1, 2};
  ret = permuteUnique(a);
  cout << "Finding unique permutations for "; printVector(a); 
  printPermutations(ret);
  
  return(0); 
}