My C++ Solution Share


  • 11
    J

    It is obvious that N numbers has N! permutations .

    Here I assume an empty vector also has one permutation. It seems OJ didn't check the empty input case. Well, it doesn't matter.

    class Solution {
    public:
        vector<vector<int> > permute(vector<int> &num) {
            // Add an empty vector as the base case (empty input)
        	vector<vector<int> > permutations(1, vector<int>());
        	// Algrithm description:
        	//	Insert the current number in different spaces of previous permutations
        	for (vector<int>::size_type index = 0; index != num.size(); ++index)
        	{
        		vector<vector<int> > subPermutations(permutations);
        		permutations.clear();
        		for (vector<vector<int> >::size_type i = 0; i != subPermutations.size(); ++i)
        		{
        			for (int offset = 0; offset != subPermutations[i].size()+1; ++offset)
        			{
        				vector<int> temp(subPermutations[i]);
        				temp.insert(temp.begin() + offset, num[index]);
        				permutations.push_back(temp);
        			}
        		}
        	}
        	return permutations;
        }
    };
    

    All comments are welcome !


  • 0
    M

    I think this wont work for (say) the test case {1,2,3,3}.


  • 0
    J

    Yes. The code cannot be applied to Permutation II when I encountered the problem. While it works for Permutation .


  • 0
    K

    here is my dp solution:

    class Solution {
    public:
        vector<vector<int> > permute(vector<int> &num) {
            int n = num.size();
            if(!n) return vector<vector<int>>();
            vector<vector<vector<int>>> dp(n);
            dp[0] = vector<vector<int> >(1,vector<int>(1,num[0]));
            for(int i = 1 ; i < n ; ++i){
                for(int j = 0 ; j < dp[i-1].size() ; ++j){
                    dp[i-1][j].insert(dp[i-1][j].begin(),num[i]);
                    dp[i].push_back(dp[i-1][j]);
                    for(int k = 1 ; k < dp[i-1][j].size() ; ++k){
                        swap(dp[i-1][j][0],dp[i-1][j][k]);
                        dp[i].push_back(dp[i-1][j]);
                        swap(dp[i-1][j][0],dp[i-1][j][k]);
                    }
                }
            }
            return dp[n-1];
        }
    };

  • 0
    Z

    Like this non-recursive solution!


  • 0
    J

    The 'insert' operation is very time consuming. So the time complexity of this solution is N times more than that of the recursive solution.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.