题目描述：

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]Output:[  [1,2,3],  [1,3,2],  [2,1,3],  [2,3,1],  [3,1,2],  [3,2,1]]

解题思路：

用回溯法。使用额外空间记录每个数值是否已经使用。

代码：

1 class Solution { 2 public: 3     vector
      
       
        > permute(vector
        
         & nums) { 4         int size = nums.size(); 5         vector
         
           flag(size, 0); 6         vector
          
           
             > ret; 7 vector
            
              tmp; 8 tmp.reserve(size); 9 permute(size, flag, tmp, ret);10 for (int i = 0; i < ret.size(); i++) {11 for (int j = 0; j < size; j++) {12 ret[i][j] = nums[ret[i][j]];13 }14 }15 return ret;16 }17 void permute(int size, vector
             
              & flag, vector
              
               & tmp, vector
               
                
                  >& ret) {18 if (accumulate(flag.begin(), flag.end(), 0) == size) {19 ret.push_back(tmp);20 }21 for (int i = 0; i < size; i++) {22 if (flag[i])23 continue;24 flag[i] = 1;25 tmp.push_back(i);26 permute(size, flag, tmp, ret);27 tmp.pop_back();28 flag[i] = 0;29 }30 }31 };
                
               
              
             
            
           
          
         
        
       
      

 改进版本：

1 class Solution { 2 public: 3     vector
      
       
        > permute(vector
        
         & nums) { 4         int size = nums.size(); 5         vector
         
           flag(size, 0); 6         vector
          
           
             > ret; 7 vector
            
              tmp; 8 tmp.reserve(size); 9 permute(size, nums, flag, tmp, ret);10 /*for (int i = 0; i < ret.size(); i++) {11 for (int j = 0; j < size; j++) {12 ret[i][j] = nums[ret[i][j]];13 }14 }*/15 return ret;16 }17 void permute(int size, const vector
             
              & nums, vector
              
               & flag, vector
               
                & tmp, vector
                
                 
                   >& ret) {18 if (accumulate(flag.begin(), flag.end(), 0) == size) {19 ret.push_back(tmp);20 return;21 }22 for (int i = 0; i < size; i++) {23 if (flag[i])24 continue;25 flag[i] = 1;26 tmp.push_back(nums[i]);27 permute(size, nums, flag, tmp, ret);28 tmp.pop_back();29 flag[i] = 0;30 }31 }32 };