k*******2 发帖数: 84 | 1 II是含duplicate的。下面这个解法过OJ没问题,但是我不是很理解它是怎么处理{1, 1
}这种情况的。
if (used[i] || (i != 0 && num[i] == num[i - 1] && used[i - 1])) continue;
我怎么觉得它会返回空{}。
估计是哪里想错了,求指教。多谢!
class Solution {
public:
vector > permuteUnique(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector used(num.size(), false);
vector path;
vector > ret;
sort(num.begin(), num.end());
sub(num, used, path, ret);
return ret;
}
void sub(vector &num, vector &used, vector &path, vector
> &ret) {
if (num.size() == path.size()) {
ret.push_back(path);
return;
}
for (int i = 0; i < num.size(); ++i) {
if (used[i] || (i != 0 && num[i] == num[i - 1] && used[i - 1]))
continue;
used[i] = true;
path.push_back(num[i]);
sub(num, used, path, ret);
used[i] = false;
path.pop_back();
}
}
}; | i****y 发帖数: 84 | 2 当前数字的前一个如果相等,而且前一个数字已经使用了,那当前数字就不要用。这样
就只有一种情况,比如有五个1,12345,数字代表这五个1的位置,那他们根据条件只
能有54321的排列。 |
|