# My elegant recursive C++ solution with inline explanation

• This recursive solution is the my first response for this problem. I was surprised when I found no similar solution posted here. It is much easier to understand than DFS-based ones, at least in my opinion. Please find more explanations here. All comments are welcome.

``````class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
vector<vector<int> > result;

permuteRecursive(num, 0, result);
return result;
}

// permute num[begin..end]
// invariant: num[0..begin-1] have been fixed/permuted
void permuteRecursive(vector<int> &num, int begin, vector<vector<int> > &result)	{
if (begin >= num.size()) {
// one permutation instance
result.push_back(num);
return;
}

for (int i = begin; i < num.size(); i++) {
swap(num[begin], num[i]);
permuteRecursive(num, begin + 1, result);
// reset
swap(num[begin], num[i]);
}
}
};
``````

• well, that's just what I've done:

``````    void dfs(int pos, vector<int> &num, vector<vector<int>> &result){
if(pos == num.size()){
result.push_back(num);
}
else{
for(int i=pos; i<num.size(); i++){
swap(num[i], num[pos]);
dfs(pos+1, num, result);
swap(num[i], num[pos]);
}
}
``````

• Really smart. Even though my idea is exactly same with yours, I used some extra space to keep the num and current permutation. Yours is much better since no extra space has been used.

• I modified your code for permutation II, but something wrong happened. Will you plz take a look at my post: https://oj.leetcode.com/discuss/19826/adding-two-lines-to-permutation-why-got-output-limit-exceed

• love the swap idea, avoid maintaining record of which indices have been visited using an extra set or list. def make code slimmer.

• How about
if (begin >= num.size()) to if (begin >= num.size()-1) will better.

• Brilliant...

• btw this assumes that there are no duplicates right? Otherwise there will be duplicates in the output?

• Right. It's not difficult to modify it to handle duplicates as https://oj.leetcode.com/discuss/20879/sharing-short-solution-using-dfs-modified-from-permutation does.

• Here is the modification to cope with duplicates http://xiaohuiliucuriosity.blogspot.com/2015/03/permutations-ii.html

• You may change the reference `vector<int>&` to `vector<int>` in `permuteRecursive()` and then you won't need the second `swap` statements. However, your way is more space-efficient.

• Thanks for smart code. Following is the Java version.

``````public class Solution {
public List<List<Integer>> permute(int[] num) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
permute(num,0,result);
return result;}

public void permute(int[] num, int begin, List<List<Integer>> result){
if(begin>=num.length){
List<Integer> list = new ArrayList<Integer>();
for(int i=0;i<num.length;i++){
list.add(num[i]);
}
result.add(list);
return;
}
for(int i=begin;i<num.length;i++){
swap(begin,i,num);
permute(num,begin+1,result);
swap(begin,i,num);

}
}

public void swap (int x, int y,int[] num){
int temp = num[x];
num[x]=num[y];
num[y]=temp;
} }``````

• can you please analyse space and time complexity? thanks

• It's hard to understand the process of recursive.

• Hi,

In the permuteRecursive( ), for nums, is the reference & necessary? I think it is ok to not pass by reference. Passing by reference can only save space, right?

• I think passing by reference also saves time because the vector on the receiving end doesn't need to copy the whole vector values. CMIIW.

• What's the time complexity of this?

• Please laugh at my answer, I think the nums maybe include repeat int,so do a repeat check

``````vector<vector<int>> permute(vector<int>& nums)
{
vector<vector<int>> vvOutput;
int iLength = nums.size();
vector<int> vTemp(iLength, 1);
ProductPermute(0, nums, vTemp, vvOutput);
return vvOutput;
}
void	ProductPermute(int iNumIndex, vector<int> nums, vector<int> vTemp, vector<vector<int>> &vvOutput)
{
int iLength = nums.size();
if(0 == iLength)
{
vvOutput.push_back(vTemp);
return;
}
for(int iIndex = 0; iIndex < iLength; iIndex++)
{
if(CheckPermuteRepeat(iNumIndex, nums[iIndex], vTemp, vvOutput))
{
vTemp[iNumIndex] = nums[iIndex];
vector<int> vCopy = nums;
vCopy.erase(vCopy.begin() + iIndex);
ProductPermute(iNumIndex + 1, vCopy, vTemp, vvOutput);
}
}
}
int CheckPermuteRepeat(int iNumIndex, int iValue, vector<int> vTemp, vector<vector<int>> vvOutput)
{
int iLine = vvOutput.size();
vTemp[iNumIndex] = iValue;
for(int iIndexLine = 0; iIndexLine < iLine; iIndexLine++)
{
int iIndexRow = 0;
for(; iIndexRow <= iNumIndex; iIndexRow++)
{
if(vvOutput[iIndexLine][iIndexRow] != vTemp[iIndexRow])
break;
}
if(iIndexRow == iNumIndex+1)
return 0;
}
return 1;
}``````

• this is basically the same as DFS

• if (begin >= num.size())
The "IF" condition can be if (begin >= num.size()-1) because even at the last index, there are no more changes made.

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