46. Permutations（全排列问题--回溯问题经典）

Given a collection of distinct 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],
  [3,2,1]
]

题目大意：求一个序列的全排列。

思路：做排列组合时，模拟该过程得到思路。首先选择集合中的某一个元素作为第一位，接着在剩下的元素中选择一个元素作为第二位，一直到为空。

上述过程显然是个递归的过程，声明帮助函数：Helper(vector<vector<int> >& result, vector<int>& tmp, vector<int>& nums)。tmp用来存储已经选定的元素，nums用来存储剩下的元素，result存储所得的情况。显然当nums为空的时候递归应该返回。

注意：关键在于对nums和tmp的处理，一旦tmp中增加了一个元素，nums就要删除该元素；每次有一个帮助函数返回时都会进行一次回溯，即nums要插入元素，tmp要删除元素。

代码如下：(采用典型的回溯来处理)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class  Solution {
public :
     void  permuteHelper(vector<vector< int > >& result,vector< int > &tmp,vector< int >& nums)
     {
         if (nums.empty())
         {
             result.push_back(tmp);
             return ;
         }
         
         for ( int  i = 0; i < nums.size(); i++)
         {
             int  val = nums[i];
             tmp.push_back(val);
             nums.erase(nums.begin()+i);
             permuteHelper(result,tmp,nums);
             nums.insert(nums.begin()+i,val);
             tmp.pop_back();
         }
     }
     vector<vector< int >> permute(vector< int >& nums) {
         vector<vector< int >> result;
         vector< int > tmp;
         permuteHelper(result,tmp,nums);
         
         return  result;
     }
};

2016-08-07 15:11:04