[LeetCode 题解]: 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。

在STL里面有一个next_permutation函数，如果数据量小的时候，这个函数还比较好用。不过当数据大后，next_permutation函数效率就不行了。

本题套用DFS模版即可。

类似的题目： Permutation II http://www.cnblogs.com/double-win/p/3793293.html , 全排列的升级版，可能出现重复数字。

class Solution {

public:

    vector<vector<int> > ans;

    vector<int> print;

    vector<int> mark;

    int length;

    void DFS(int len,vector<int> &num){

        if(len==length)

        {

            ans.push_back(print);

            return;

        }

        for(int i=;i<length;i++)

        {

           if(mark[i]==)

           {

              print[len]= num[i];

              mark[i]=;

              DFS(len+,num);

              mark[i]=;

            }

        }

    }

    vector<vector<int> > permute(vector<int> &num) {

        length=num.size();

        ans.clear();

        if(length<=) return ans;

        print.clear();

        print.resize(length);

        mark.clear();

        mark.resize(length);

        DFS(,num);

        return ans;

    }

};

转载请注明出处： http://www.cnblogs.com/double-win/ 谢谢！

巴特西

[LeetCode 题解]: Permutations

最新文章

热门文章