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 >& result, vector& tmp, vector& nums)。tmp用来存储已经选定的元素，nums用来存储剩下的元素，result存储所得的情况。显然当nums为空的时候递归应该返回。
注意：关键在于对nums和tmp的处理，一旦tmp中增加了一个元素，nums就要删除该元素；每次有一个帮助函数返回时都会进行一次回溯，即nums要插入元素，tmp要删除元素。
代码如下：(采用典型的回溯来处理)
class Solution {
public:
void permuteHelper(vector >& result,vector &tmp,vector& 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> permute(vector& nums) {
vector> result;
vector tmp;
permuteHelper(result,tmp,nums);
return result;
}
};2016-08-07 15:11:04
当前题目：leetCode46.Permutations回溯问题|Medium
本文地址：
http://cdxtjz.cn/article/peposg.html
