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

 

与Next Permutation一样，n个元素的排列共有n！个，所以只要执行n！次next_permutation就行。

 

1 class Solution { 2 public: 3     bool nextPermutation(vector
     
       &num) { 4         if (num.size() < 2) { 5             return false; 6         } 7         int i, k; 8         bool flag = true; 9         for (i = num.size() - 2; i >= 0; --i) {10             if (num[i] < num[i + 1]) {11                 break;12             }13         }14         if (i < 0) {15             flag = false;16         }17         for (k = num.size() - 1; k > i; --k) {18             if (num[k] > num[i]) {19                 break;20             }21         }22         swap(num[i], num[k]);23         reverse(num.begin() + i + 1, num.end());24         return flag;25     }26     27     long long getNum(int n) {28         long long res = 1;29         while (n > 0) {30             res *= n;31             n--;32         }33         return res;34     }35     36     vector
      
       
         > permute(vector
        
          &num) {37         vector
         
          
            > res;38 res.push_back(num);39 long long n = getNum(num.size());40 while (--n) {41 nextPermutation(num);42 res.push_back(num);43 }44 return res;45 }46 };