# A simple recursion solution (C++)

• Notes:
(Suppose input is 1,2,1,2)

1. 2 lines modification to Permutation I;
2. Build the answer bottom-up: {(1)} -> {(2, 1), (1, 2)} -> {(1, 2, 1), (2, 1, 1), (1, 1, 2)};
3. To handle the duplication, find the last position plus 1 (k+1) of the duped value of current solution (s), and starting generating new solution (t).

Code:

``````vector<vector<int> > permuteUnique(vector<int> &num) {
vector<vector<int> > res;
if (!num.empty()) {
vector<int> s(1, num[0]);
permuteUnique_rec(s, num, res);
}
return res;
}

// s is current solution
// num is the input
// res is the results collection
void permuteUnique_rec(vector<int> s, vector<int> &num, vector<vector<int> > &res) {
size_t n = s.size();
if (n == num.size()) {
res.push_back(s);
}
else {
size_t i, j;
int k = n - 1;
while (k >= 0 && num[n] != s[k]) k--;           // find the last equal-value element position

for (i = k + 1; i <= n; i++) {
vector<int> t(n + 1);
for (j = 0; j < i; j++)  t[j] = s[j];       // copy the left
t[j] = num[n];                              // copy the current value
for (j = i; j < n; j++)  t[j + 1] = s[j];   // copy the right
permuteUnique_rec(t, num, res);
}
}
}``````

• Copy your idea but make it with DP:

``````class Solution
{
public:
// Dynamic programming
// Based on the idea at: https://oj.leetcode.com/discuss/16264/a-simple-recursion-solution-c
vector<vector<int> > permuteUnique(vector<int> &num)
{
vector<vector<int>> result;
int n = num.size();
if(!n)
{
return result;
}
result.push_back(vector<int>(1, num[0]));
for(int i = 1; i < n; i++)
{
int size = result.size();
for(int j = 0; j < size; j++)
{
vector<int> base = result[j];
base.push_back(num[i]);
result[j] = base;
int k = base.size() - 2;
while(k >= 0 && base[k] != num[i])
{
base[k + 1] = base[k];
result.push_back(base);
result.back()[k] = num[i];
k--;
}
}
}
return result;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.