LeetCode OJ:Permutations

Permutations

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

class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int>> result;
        sort(num.begin(),num.end());
        
        do{
            result.push_back(num);
        }while(next_permutation(num.begin(),num.end()));
        
        return result;
    }
};

class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int>> result;
        sort(num.begin(),num.end());
        
        do{
            result.push_back(num);
        }while(next_permutation(num.begin(),num.end()));
        
        return result;
    }
private:
    template<typename BidirIt>  
    bool next_permutation(BidirIt first, BidirIt last)  
    {  
        const auto rfirst = reverse_iterator<BidirIt>(last);  
        const auto rlast = reverse_iterator<BidirIt>(first);  
          
        auto pivot = next(rfirst);  
          
        while(pivot != rlast && *pivot >= *prev(pivot))//step1  
            ++pivot;  
          
        if(pivot == rlast){  
            reverse(rfirst,rlast);  
            return false;  
        }  
          
        auto change = find_if(rfirst,pivot,bind2nd(greater<int>(),*pivot));//step2  
          
        swap(*change,*pivot);//step3  
        reverse(rfirst,pivot);//step4  
          
        return true;  
    }  
};