Given a collection of numbers that might contain duplicates, return all possible unique permutations.(https://leetcode.com/problems/permutations-ii/)

permutationII_leetcode.cpp

/*
Permutation II ::

Problem Statement:: 
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
(https://leetcode.com/problems/permutations-ii/)

Example:

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

I have implemented recursion tree using both the conditions :
for Condition one - if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1] ) continue; .... Check this link - https://ibb.co/k4zv00
for condition two - if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] ) continue;....Check this link - https://ibb.co/ncMm7f
All your doubts will be cleared.

Time Complexity Analysis::

The worst-case time complexity is O(n!).

	T(n)= n ( T(n-1) + c ), n>= 1       (Recurrence relation for code below)
	    = 1               , n = 0
Solving it using back substituition gives , T(n) = O(n!) (ie total no of permutations also)
*/

#include<bits/stdc++.h>
using namespace std;

void display_vector(vector<int> &arr )
{
    for(int i = 0 ; i<arr.size() ; i++)
        {
            cout<<arr[i]<<" " ;
        }
        cout<<"\n" ;
}

void display_vectorOfVector(vector<vector<int> > &arr )
{
    for(int i = 0 ; i<arr.size() ; i++)
        {
            for(int j = 0 ; j<arr[i].size() ; j++)
                cout<<arr[i][j]<<" " ;
            cout<<"\n" ;
        }
}
void permuteUnique_helper(vector<vector<int> > &res , vector<int > &step , vector<int > &used , vector<int > &num )
{
    if (step.size() == num.size())
	{
		res.push_back(step);
		return;
    }
    for (int i = 0; i < num.size(); i++) {
        if (used[i] || i>0 && num[i] == num[i-1] && !used[i-1]) continue;
        used[i] = 1 ;
        step.push_back(num[i]) ;
        permuteUnique_helper(res , step , used , num );
        used[i] = 0 ;
        step.pop_back() ;
    }
}
vector<vector<int> > permuteUnique(vector<int> &num) {
    sort(num.begin(), num.end());
    vector<vector<int> >res;
    vector<int> step ;
    vector<int> used( num.size() , 0) ;
    sort(num.begin() , num.end()) ;
    permuteUnique_helper(res , step , used , num );
    return res;
}

int main()
{
	vector<int> A ;
	int n ;
	cout<<"enter the number of elements :" ;
	cin>>n ;
	cout<<endl ;
	for(int i = 0 ; i < n ; i++)
	{
	    int temp ;
	    cout<<"enter element :" ;
	    cin>>temp ;
	    A.push_back(temp) ;
	    cout<<endl ;
	}
    vector< vector<int> > ans = permuteUnique(A) ;
	cout<<"Output of program ==>\n" ;
	display_vectorOfVector(ans) ;
	return 0 ;
}