[leetcode] Permutations

Permutations

Given a collection of numbers, return all possible 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].

思路：

dfs搜索。visited[]数组表示对应的数字是否已经使用，visited[i]==true，表示num[i]已经使用。一直递归搜索，寻找没有使用过的数字，组成全排列。

这里给visited数组赋值的时候，开始写成了sizeof(int)，提交出现runtime error，但是在vs2010下可以得出正确结果；后来发现换成了sizeof(bool)就通过了。这个估计和编译器有关，可以研究一下。

题解：

class Solution {
public:
    vector<vector<int> > res;
    vector<int> tmp;
    void dfs(vector<int> &num, bool visited[], int index) {
        if(index==num.size()) {
            res.push_back(tmp);
            return;
        }
        for(int i=0;i<num.size();i++) {
            if(visited[i])
                continue;
            visited[i] = true;
            tmp.push_back(num[i]);
            dfs(num, visited, index+1);
            tmp.pop_back();
            visited[i] = false;
        }
    }
    vector<vector<int> > permute(vector<int> &num) {
        int n = num.size();
        bool *visited = new bool [n];
        memset(visited, false, sizeof(bool)*n);
        dfs(num, visited, 0);
        return res;
    }
};

后记：

提交出现runtime error时，就在网上找了一下大神们的解法，发现了一种交换排序的方法，似乎逻辑更严密一些，尤其是在全排列系列的题目特别有帮助。这里就不放代码了，给出链接。