09月22日, 2014 230次
题目给定一个可包含重复数字的序列，返回所有不重复的全排列。示例:输入: [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 函数逃避思考的问题了。