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

题目翻译: 给定一个整形数组，要求求出这个数组的所有变形体，具体例子看上文中给出的例子就可以.

题目分析: 这道题很直接，几乎算是没有坑，相信大家都可以理解题目的要求. Permutation的解题方法和Combination几乎是相同的，唯一需要注意的是，Permutation需要加一个bool类型的数组来进行记录哪个元素访问了，哪个没有，这样才不会导致重复出现，并且不同于Combination的一点是，Permutation不需要排序.

解题思路: 遇到这种问题，很显然，第一个想法我们首先回去想到DFS,递归求解，对于数组中的每一个元素，找到以他为首节点的Permutations,这就要求在递归中，每次都要从数组的第一个元素开始遍历，这样，，就引入了另外一个问题，我们会对于同一元素访问多次，这就不是我们想要的答案了，所以我们引入了一个bool类型的数组，用来记录哪个元素被遍历了(通过下标找出对应).在对于每一个Permutation进行求解中，如果访问了这个元素,我们将它对应下表的bool数组中的值置为true,访问结束后，我们再置为false.

时间复杂度分析: 这道题同Combination,所以对于这道题的解答，时间复杂度同样是O(n!)

代码如下:

class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int>> permutations;
        if(num.size() == 0) //invalid corner case check
            return permutations;
        vector<int> curr;
        vector<bool> 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<vector<int>>& ret, vector<int> curr, vector<bool> isVisited, vector<int> 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].

题目翻译: 给定一个整形数组，这个数组中可能会包含重复的数字，要求我们返回的是这个数组不同的Permutations,也就是说每一种可能的permutation在最后的答案中只能出现一次.上文的例子能清晰的告诉读者不同的地方.

题目分析: 对于这道题。也是要求permutation,大体上的解题思路和Permutations是相同的，但是不同点在哪里呢？ 不同点为：

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

对于这两点要求，Permutations的解法是无法解决的，所以我们就要考虑怎样满足以上两个要求. 我们可以对整个input数组进行排序，在求解答案的时候，只要一个元素的permutation求出来了，在这个元素后面和这个元素相同的元素，我们完全都可以pass掉，其实这个方法在sum和combination里面已经是屡试不爽了.

解题思路: 除了加上对于重复答案的处理外，剩下思路同Permutation一模一样。

时间复杂度: O(n!)

代码如下:

class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int>> permutations;
        if(num.size() == 0)
            return permutations;
        vector<int> curr;
        vector<bool> 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<vector<int>>& ret, vector<int> curr, vector<int> num, vector<bool> 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;
            }
        }
    }
};