# Permutation

# Permutation这个分支是在backtracking下的一个子分支，其具体的解题方法和Combination几乎是同出一辙，一个思路，对于给定数组用DFS方法一层一层遍历，在这个section当中，我们将对于leetcode上出现的permutation问题进行逐个分析与解答.

# Permutations

> given a collection of numbers, return all posibile permutations.

> For example, [1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

```c++

class Solution {
public:
vector > permute(vector &num) {
vector> permutations;
if(num.size() == 0) //invalid corner case check
return permutations;
vector curr;
vector isVisited(num.size(), false); //using this bool type array to check whether or not the elments has been visited
backTracking(permutations,curr,isVisited,num);
return permutations;
}

void backTracking(vector>& ret, vector curr, vector isVisited, vector num)
{
if(curr.size() == num.size())
{
ret.push_back(curr);
return;
}

for(int i = 0; i < num.size(); ++i)
{
if(isVisited[i] == false)
{
isVisited[i] = true;
curr.push_back(num[i]);
backTracking(ret,curr,isVisited,num);
isVisited[i] = false;
curr.pop_back();
}
}
}

};
```

# Permutations II

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

1. 这个给定的数组中可能会含有相同的数字.
2. 最后答案不接受重复相同的答案组.

O(n!)

```c++

class Solution {
public:
vector > permuteUnique(vector &num) {
vector> permutations;
if(num.size() == 0)
return permutations;
vector curr;
vector isVisited(num.size(), false);
/* we need to sort the input array here because of this array
contains the duplication value, then we need to skip the duplication
value for the final result */
sort(num.begin(),num.end());
DFS(permutations,curr,num,isVisited);
return permutations;
}

void DFS(vector>& ret, vector curr, vector num, vector isVisited)
{
if(curr.size() == num.size())
{
ret.push_back(curr);
return;
}

for(int i = 0; i < num.size(); ++i)
{
if(isVisited[i] == false)
{
isVisited[i] = true;
curr.push_back(num[i]);
DFS(ret,curr,num,isVisited);
isVisited[i] = false;
curr.pop_back();
while(i < num.size()-1 && num[i] == num[i+1]) //we use this while loop to skip the duplication value in the input array.
++i;
}
}
}
};

```