Permutations IIMar 17 '124943 / 12877
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].
生成的方法其实和permutation差不多，最大的差别就是unique
思考一下，生成时候的流程：每次从后面去一个数num[i]，替换num[cur]。
因为num内存在相同的数，也就是说，num[i] 可能和num[j]相同。
因此如果num[i]已经在cur这个位置上出现过，这num[j]可以直接跳过去。
class Solution {
public:
vector<vector<int> > permuteUnique(vector<int> &num) {
int len = num.size();
vector<vector<int> > res;
sort(num.begin(), num.end());
gen(res, num, 0, len);
return res;
}
bool isSwap(vector<int>& num, int s, int e) {
int i = s;
while (num[i] != num[e] && i < e) i++;
if (i == e) return true;
else return false;
}
void gen(vector<vector<int> > &res, vector<int>& num, int cur, int len) {
if (cur == len) {
res.push_back(num);
return;
}
for (int i = cur; i < len; i++) {
if (!isSwap(num, cur, i)) continue;
swap(num[cur], num[i]);
gen(res, num, cur+1, len);
swap(num[cur], num[i]);
}
}
};
PermutationsMar 17 '125872 / 13772
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:
vector<vector<int> > permute(vector<int> &num) {
int len = num.size();
vector<vector<int> > res;
gen(res, num, 0, len);
return res;
}
void gen(vector<vector<int> > &res, vector<int>& num, int cur, int len) {
if (cur == len) {
res.push_back(num);
return;
}
for (int i = cur; i < len; i++) {
swap(num[cur], num[i]);
gen(res, num, cur+1, len);
swap(num[cur], num[i]);
}
}
};