LintCode 16 带重复元素的排列 LintCode

题目:permuteUnique 要求:

给出一个具有重复数字的列表，找出列表所有不同的排列。

样例:

给出列表 [1,2,2]，不同的排列有：[ [1,2,2], [2,1,2], [2,2,1] ]

算法要求:

使用递归和非递归分别完成该题。

解题思路:

我是直接在全排列基础上改的。

算法如下:

vector > mainVec; int size; void permute(vector &nums, int m) { int temp; if (m == nums.size()) { for (int i = 0; i < size; i++) { if (mainVec[i] == nums) { return; } } size++; mainVec.push_back(nums); } else { for (int i = m; i < nums.size(); i++) { temp = nums[m]; nums[m] = nums[i]; nums[i] = temp; permute(nums, m+1); temp = nums[m]; nums[m] = nums[i]; nums[i] = temp; } } }vector > permuteUnique(vector nums) { mainVec.clear(); size = 0; permute(nums, 0); return mainVec; }