sundeepblue
3/16/2014 - 10:09 PM

## Given a collection of numbers that might contain duplicates, return all possible unique permutations. For example, [1,1,2] have the followi

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].

``````// idea, first, sort the array!
// it seems like I do not need the visit array!!!

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

bool has_duplicates(vector<int> &nums, int begin, int i) {
for(int j=begin; j<i; j++)
if(nums[j] == nums[i]) return true;
return false;
}

void dfs(vector<vector<int>> &res, vector<int> &one, vector<bool> visit,
int start, int n, vector<int> &nums) {

if(start == n) {
res.push_back(one);
return;
}
for(int i=start; i<n; i++) {
//if(visit[i] == true) continue; // gist
//if(i>start && nums[i] == nums[i-1] ) continue; // wrong!!!!!
if(has_duplicates(nums, begin, i)) continue;
swap(num[start], num[i]);

one.push_back(nums[start]);
dfs(res, one, visit, start+1, n, nums);
one.pop_back();

swap(num[start], num[i]);
}
}

vector<vector<int>> get_premutation(vector<int> &nums) {
vector<vector<int>> res;
vector<int> one;
vector<bool> visit(nums.size(), false);
sort(nums.begin(), nums.end()); // gist!!!!
dfs(res, one, visit, 0, nums.size(), nums);
return res;
}

int main()
{
vector<int> nums = {1, 1, 3, 2};
vector<vector<int>> res = get_premutation(nums);
for(vector<int> v : res) {
for(auto i : v) cout << i << " ";
cout << endl;
}
return 0;
}
``````