【Permutations】cpp

题目：

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

代码：

class Solution {

public:

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

            vector<vector<int> > ret;

            vector<int> none;

            ret.push_back(none);

            for ( size_t i = ; i < nums.size(); ++i ){

                vector<vector<int> > tmp = ret;

                ret.clear();

                for ( size_t j = ; j < tmp.size(); ++j ){

                    for ( size_t k = ; k < i+; ++k ){

                        vector<int> ori = tmp[j];

                        ori.insert(ori.begin()+k, nums[i]);

                        ret.push_back(ori);

                    }

                }

            }

            return ret;

    }

};

tips：

参考（http://bangbingsyb.blogspot.sg/2014/11/leetcode-permutations-i-ii.html）

采用增量构造法（暴力法解决）：每次新增一个元素，对上次已有的permutations，从0到size挨个位置插入一遍。

[] // 注意一开始要给ret一个空的vector<int> 这样才循环才能run起来

[]

[ 1],[1 ]

[ 2 1], [2 1], [2 1 ], [ 1 2 ], [1 2], [1 2 ]

=======================================

又写了一版DFS的代码，如下：

class Solution {

public:

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

            vector<vector<int> > ret;

            vector<int> tmp;

            vector<bool> used(nums.size(), false);

            Solution::perpermute(nums, ret, tmp, used);

            return ret;

    }

    static void perpermute(

            vector<int>& nums,

            vector<vector<int> >& ret,

            vector<int>& tmp,

            vector<bool>& used )

    {

            if ( tmp.size()==nums.size() )

            {

                ret.push_back(tmp);

                return;

            }

            for ( int i =; i < nums.size(); ++i )

            {

                if (used[i]) continue;

                tmp.push_back(nums[i]);

                used[i] = true;

                Solution::perpermute(nums, ret, tmp, used);

                tmp.pop_back();

                used[i] = false;

            }

    }

};

tips：

tmp用于不断构造一个permutation，每一层代表permutation的一个位置，每层递归添加一个元素。

如果判断某个元素是否能被添加到tmp的后面呢？这里的办法是维护一个bool数组：每个位置判断nums对应位置上的元素是否被使用。

dfs终止条件，如果tmp的size已经为整个nums的size了，证明构造出来一个排列，可以返回

===================================================

第二次过这道题，先用暴力增量法写了一个。这个跟subset的方法类似，可以沿用这个套路。

class Solution {

public:

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

            vector<vector<int> > ret;

            vector<int> none;

            ret.push_back(none);

            for ( int i=; i<nums.size(); ++i )

            {

                vector<vector<int> > tmp = ret;

                ret.clear();

                for ( int j=; j<tmp.size(); ++j )

                {

                    for ( int k=; k<tmp[j].size(); ++k )

                    {

                        vector<int> curr = tmp[j];

                        curr.insert(curr.begin()+k, nums[i]);

                        ret.push_back(curr);

                    }

                    vector<int> curr = tmp[j];

                    curr.insert(curr.end(), nums[i]);

                    ret.push_back(curr);

                }

            }

            return ret;

    }

};

再用dfs写一遍。

class Solution {

public:

        vector<vector<int> > permute(vector<int>& nums)

        {

            vector<vector<int> > ret;

            vector<int> tmp;

            vector<bool> used(nums.size(), false);

            Solution::dfs(ret, nums, used, tmp);

            return ret;

        }

        static void dfs(

            vector<vector<int> >& ret,

            vector<int>& nums,

            vector<bool>& used,

            vector<int>& tmp)

        {

            if ( tmp.size()==nums.size() )

            {

                ret.push_back(tmp);

                return;

            }

            for ( int i=; i<nums.size(); ++i )

            {

                if (used[i]) continue;

                tmp.push_back(nums[i]);

                used[i] = !used[i];

                Solution::dfs(ret, nums, used, tmp);

                tmp.pop_back();

                used[i] = !used[i];

            }

        }

};

巴特西

【Permutations】cpp

最新文章

热门文章