题目

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

解题代码与测试

//
// Created by tannzh on 2020/7/9.
//

/*
 *
 全排列 II
 给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:
输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]
 */

#include <vector>
#include <iostream>
#include <algorithm>

using std::next_permutation;
using std::sort;
using std::vector;

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> retv;
        sort(nums.begin(), nums.end());
        do {
            retv.push_back(nums);
        } while (next_permutation(nums.begin(), nums.end()));
        return retv;
    }
};

int main(int argc, char **argv)
{
    Solution s;
    std::vector<int> vec{1,1,2};
    for (const auto &v : s.permuteUnique(vec)) {
        for (auto i : v)
            std::cout << i << " ";
        std::cout << std::endl;
    }
    return 0;
}

解题思路分析

又是排列组合，但使用 上一题中的解法却依然可以。

在那道题里，我说先偷个懒，使用 STL 中的算法，后面再详细补充。而这道题，我依然想偷懒一次。

在这道题中，我基本实现了 std::next_permutation。所以也并不存在无耻的使用 STL 函数逃避思考的问题了。