Tuesday, May 14, 2013

Leetcode: Permutations in C++



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

void cal(vector<int> &num, vector<int>& cur, vector<int>& visited, vector<vector<int> >& result)
    {
        if(cur.size()==num.size())
        {
            result.push_back(cur);
            return;
        }
        for(int i=0;i<num.size();i++)
        {
            if(visited[i]!=1)
            {
                cur.push_back(num[i]);
                visited[i] =1;
                cal(num, cur, visited, result);
                cur.pop_back();
                visited[i] =0;
            }
        }
    }
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int> > result;
        int len = num.size();
        vector<int> visited(len, 0);
        vector<int> cur;
        cal(num, cur, visited, result);
        return result;
    }

No comments:

Post a Comment