[LintCode] Permutations

4662 단어 code
http://www.lintcode.com/en/problem/permutations/#
Given a list of numbers, return all possible permutations.
Example
For nums = [1,2,3] , the permutations are:
[

  [1,2,3],

  [1,3,2],

  [2,1,3],

  [2,3,1],

  [3,1,2],

  [3,2,1]

]

전체 배열 을 구 하려 면 DFS 로 해결 할 수 있 습 니 다. 코드 를 보십시오.
class Solution {

public:

    /**

     * @param nums: A list of integers.

     * @return: A list of permutations.

     */

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

        // write your code here

        vector<vector<int>> paths;

        if (nums.empty()) {

            return paths;

        }

        

        vector<int> index;

        vector<int> path;

        permuteHelper(nums, index, path, paths);

        return paths;

        

    }

    

private:

    void permuteHelper(const vector<int> &nums,

                       vector<int> &index,    

                       vector<int> &path,

                       vector<vector<int>> &paths) {

        if (path.size() == nums.size()) {

            paths.push_back(path);

            return;

        }

        

        for (int ix = 0; ix < nums.size(); ix++) {

            if (find(index.begin(), index.end(), ix) == index.end()) {

                index.push_back(ix);

                path.push_back(nums[ix]);

                permuteHelper(nums, index, path, paths);

                index.pop_back();

                path.pop_back();

            }

        }                   

    }

};

, , vector, vector , o(n) , hashset , :

class Solution {

public:

    /**

     * @param nums: A list of integers.

     * @return: A list of permutations.

     */

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

        // write your code here

        vector<vector<int>> paths;

        if (nums.empty()) {

            return paths;

        }

        

        unordered_set<int> index;

        vector<int> path;

        permuteHelper(nums, index, path, paths);

        return paths;

    }

    

private:

    void permuteHelper(const vector<int> &nums,

                 unordered_set<int> &index,

                 vector<int> &path,

                 vector<vector<int>> &paths) {

        if (path.size() == nums.size()) {

            paths.push_back(path);

            return;

        }       

        

        for (int ix = 0; ix < nums.size(); ix++) {

            if (index.count(ix) == 0) {

                index.insert(ix);

                path.push_back(nums[ix]);

                permuteHelper(nums, index, path, paths);

                index.erase(ix);

                path.pop_back();

            }

        }

    }

};

? hashset, :

class Solution {

public:

    /**

     * @param nums: A list of integers.

     * @return: A list of permutations.

     */

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

        // write your code here

        vector<vector<int>> paths;

        if (nums.empty()) {

            return paths;

        }

        

        bool *visited = new bool[nums.size()]();

        vector<int> path;

        permuteHelper(nums, visited, path, paths);

        return paths;

    }

    

private:

    void permuteHelper(const vector<int> &nums,

                       bool *visited,

                       vector<int> &path,

                       vector<vector<int>> &paths) {

        if (path.size() == nums.size()) {

            paths.push_back(path);

            return;

        }       

        

        for (int ix = 0; ix < nums.size(); ix++) {

            if (visited[ix] == false) {

                visited[ix] = true;

                path.push_back(nums[ix]);

                permuteHelper(nums, visited, path, paths);

                visited[ix] = false;

                path.pop_back();

            }

        }

    }

};

 

좋은 웹페이지 즐겨찾기