Permutations

Description:

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

思路分析：

_{求一组数据}a_1,a_2,...,a_{n的全排列可按如下步骤求解：}

1.求出a₂,a₃,...a_n的全排列{P1,P2, ... ,Pj};

2. 将a1插入进去，得到新的全排列{a1P1, a1P2,..., a1Pj};

3. 交换a1和ai（1<i<=n），重复执行上述1,2两步，再交换a1和ai，即可得到所有的排列组合。

Code:

1   //定义一个接口函数
2   vector<vector<int>> permute(vector<int>& nums) {
3      return permute(nums, 0, nums.size()-1);
4     }

 1 vector<vector<int>> permute(vector<int>& nums,int lIndex, int rIndex)
 2     {
 3         if (lIndex <= rIndex)
 4         {
 5             vector< vector<int> >result, tempResult;
 6             vector<int>temp;
 7         
 8             if (lIndex == rIndex)
 9             {
10                 temp.push_back(nums[lIndex]);
11                 result.push_back(temp);
12                 return result;
13             }
14             else
15             {
16                 for (int i = lIndex; i <= rIndex; ++i)
17                 {
18                     if (i != lIndex)
19                     {//注意当i和lIndex相等时，一个数将和它本身异或，则结果一定为0
20                         nums[i]^=nums[lIndex];
21                         nums[lIndex]^=nums[i];
22                         nums[i]^=nums[lIndex];
23                     }
24                     tempResult = permute(nums, lIndex+1, rIndex);
25                    
26                     for (int j = 0; j < tempResult.size(); ++j)
27                     {
28                         tempResult[j].insert(tempResult[j].begin(),nums[lIndex]);
29                         result.push_back(tempResult[j]);
30                     }
31                     //将两个元素交换回来
32                     if (i != lIndex)
33                     {
34                         nums[i]^=nums[lIndex];
35                         nums[lIndex]^=nums[i];
36                         nums[i]^=nums[lIndex];
37                     }
38                 }
39                 return result;
40             }
41         }
42     }