Combination Sum IIPermutationsPermutations II题目描述解决方法
题目描述：
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] ] Subscribe to see which companies asked this question.
class Solution {public: void permutation(vector<vector<int>> &rel, vector<int> &nums, int stt, int last, vector<int> &tmp) { if(stt == last) { rel.push_back(nums); return; } for(int i = stt; i < last; i++) { swap(nums[stt], nums[i]); permutation(rel, nums, stt+1, last, tmp); swap(nums[stt], nums[i]); } } vector<vector<int>> permute(vector<int>& nums) { int nums_len = nums.size(); vector<vector<int>> rel; vector<int> tmp; permutation(rel, nums, 0, nums_len, tmp); return rel; }};法一：使用set去掉重复部分。
class Solution {public: void permutation2(set<vector<int> > &rel, int stt, const int &last, vector<int>&nums) { if(stt == last) { rel.insert(nums); return; } for(int i = stt; i < last; i++) { swap(nums[i], nums[stt]); permutation2(rel, stt+1, last, nums); swap(nums[i], nums[stt]); } } vector<vector<int>> permuteUnique(vector<int>& nums) { int nums_len = nums.size(); set<vector<int>> tmp; permutation2(tmp, 0, nums_len, nums); vector<vector<int> > rel(tmp.begin(), tmp.end()); return rel; }};这种做法速度慢，而且浪费空间。所以正确的做法应该是在回溯的部分使用剪枝去除冗余。
法二： 纯粹调用函数：
public: vector<vector<int>> permuteUnique(vector<int>& nums) { auto beg = nums.begin(); auto end = nums.end(); vector<vector<int>> ret; sort(beg, end); do { ret.push_back(nums); } while (next_permutation(beg, end)); return ret; }};法三：击败91%的代码：
class Solution {public: vector<vector<int> > permuteUnique(vector<int> &num) { int n = num.size(); vector<vector<int>> res; sort(num.begin(), num.end()); //sort the list permuteUnique(num, res, n, 0); return res; } void permuteUnique(vector<int> &num, vector<vector<int>> &res, int n, int s) { if (s == n) { res.push_back(num); return; } for (int j = s; j < n; j++) { if (j > s & num[j] == num[j-1]) continue; //PRevent duplicates move(num, j, s); //set the s-th element in the permutation to be //num[j], while leaving the rest elements sorted permuteUnique(num, res, n, s+1); move(num, s, j); //reset } } void move(vector<int> &num, int j, int i) { num.insert(num.begin() + i + (i > j), num[j]); num.erase(num.begin() + j + (j > i)); }};法四：击败92.94%。这里需要注意的是在函数permutation2里面，如果last使用&的话会比较慢，变成46%。
class Solution {public: void permutation2(vector<vector<int> > &rel, int stt, int last, vector<int>&nums) { if(stt == last) { rel.push_back(nums); return; } for(int i = stt; i < last; i++) { if(i > stt & nums[i] == nums[i-1]) continue; move(nums, i, stt);//swap(nums[stt], nums[i]); permutation2(rel, stt+1, last, nums); move(nums, stt, i);//swap(nums[stt], nums[i]); } } void move(vector<int> &num, int j, int i) { num.insert(num.begin() + i + (i > j), num[j]); num.erase(num.begin() + j + (j > i)); } vector<vector<int>> permuteUnique(vector<int>& nums) { int nums_len = nums.size(); vector<vector<int> > rel; sort(nums.begin(), nums.end()); permutation2(rel, 0, nums_len, nums); return rel; }};法五：使用普通的DFS计算。击败92.94%的代码
class Solution {public: void permutation2(vector<vector<int> > &rel, int stt, const int last, vector<int>nums) { if(stt == last) { rel.push_back(nums); return; } for(int i = stt; i < last; i++) { if(i != stt && nums[i] == nums[stt]) continue; swap(nums[stt], nums[i]); permutation2(rel, stt+1, last, nums); } } vector<vector<int>> permuteUnique(vector<int>& nums) { int nums_len = nums.size(); vector<vector<int> > rel; sort(nums.begin(), nums.end()); permutation2(rel, 0, nums_len, nums); return rel; }};新闻热点
疑难解答
