Permutations II

描述

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].

next_permutation()

直接使用std::next_permutation()，代码与上一题相同。

重新实现next_permutation()

重新实现std::next_permutation()，代码与上一题相同。

递归

递归函数permute()的参数p，是中间结果，它的长度又能标记当前走到了哪一步，用于判断收敛条件。

扩展节点，每次从小到大，选一个没有被用光的元素，直到所有元素被用光。

本题不需要判重，因为状态装换图是一颗有层次的树。

  1. // Permutations II
  2. // 深搜，时间复杂度O(n!)，空间复杂度O(n)
  3. class Solution {
  4. public:
  5.     vector<vector<int> > permuteUnique(vector<int>& nums) {
  6.         sort(nums.begin(), nums.end());
  8.         unordered_map<int, int> count_map; // 记录每个元素的出现次数
  9.         for (int i : nums) {
  10.             if (count_map.find(i) != count_map.end())
  11.                 count_map[i]++;
  12.             else
  13.                 count_map[i] = 1;
  14.         }
  16.         // 将map里的pair拷贝到一个vector里
  17.         vector<pair<int, int> > counters;
  18.         for (auto p : count_map) {
  19.             counters.push_back(p);
  20.         }
  21.         sort(counters.begin(), counters.end());
  23.         // 每个元素选择了多少个
  24.         unordered_map<int, int> selected;
  25.         for (auto p : counters) {
  26.             selected[p.first] = 0;
  27.         }
  29.         vector<vector<int>> result; // 最终结果
  30.         vector<int> p;  // 中间结果
  32.         n = nums.size();
  33.         permute(counters, selected, p, result);
  34.         return result;
  35.     }
  37. private:
  38.     size_t n;
  39.     typedef vector<pair<int, int> >::const_iterator Iter;
  41.     void permute(const vector<pair<int, int> > &counters,
  42.             unordered_map<int, int> &selected, 
  43.             vector<int> &p, vector<vector<int> > &result) {
  44.         if (n == p.size()) {  // 收敛条件
  45.             result.push_back(p);
  46.         }
  48.         // 扩展状态
  49.         for (auto counter : counters) {
  50.             if (selected[counter.first] < counter.second) {
  51.                 p.push_back(counter.first);
  52.                 selected[counter.first]++;
  53.                 permute(counters, selected, p, result);
  54.                 p.pop_back(); // 撤销动作，返回上一层
  55.                 selected[counter.first]--;
  56.             }
  57.         }
  58.     }
  59. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/brute-force/permutations-ii.html