这是使用DFS来解数组类题的典型题目，像求子集，和为sum的k个数也是一个类型
解题步骤：
1：有哪些起点，例如，数组中的每个元素都有可能作为起点，那么用个for循环就可以了。
2：是否允许重复组合
3：处理某个数，判断结果
4：dfs递归
5：还原现场
一：Permutations
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].
代码：
class Solution { public: void dfs(vector<int>& nums,int numsSize,int startPos,vector<vector<int>>& res,vector<int>& oneOfRes) { for(int i=startPos;i<numsSize;i++){ oneOfRes.push_back(nums[i]); swap(nums[i],nums[startPos]); if(oneOfRes.size()==numsSize){ res.push_back(oneOfRes); }else{ dfs(nums,numsSize,startPos+1,res,oneOfRes); } swap(nums[i],nums[startPos]); oneOfRes.pop_back(); } } vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> res; vector<int> oneOfRes; int numsSize = nums.size(); dfs(nums,numsSize,0,res,oneOfRes); return res; } };
二：Permutations II
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,[1,1,2] have the following unique permutations:[1,1,2], [1,2,1], and [2,1,1].
class Solution { public: void dfs(vector<int> nums,int numsSize,int startPos,vector<vector<int>>& res,vector<int>& oneOfRes) { sort(nums.begin()+startPos,nums.end()); for(int i=startPos;i<numsSize;i++){ if(i>startPos && nums[i]==nums[i-1]){ continue; } oneOfRes.push_back(nums[i]); swap(nums[i],nums[startPos]); if(oneOfRes.size()==numsSize){ res.push_back(oneOfRes); }else{ dfs(nums,numsSize,startPos+1,res,oneOfRes); } swap(nums[i],nums[startPos]); oneOfRes.pop_back(); } } vector<vector<int>> permuteUnique(vector<int>& nums) { // sort(nums.begin(),nums.end()); vector<vector<int>> res; vector<int> oneOfRes; int numsSize = nums.size(); dfs(nums,numsSize,0,res,oneOfRes); return res; } };
原文：http://www.cnblogs.com/zengzy/p/4961781.html