47. 全排列ii

1. 题目描述

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

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

2. 解题思路

计算一个map，统计各个元素的出现次数。使用DFS遍历时，每添加一个元素当前元素count-1，然后递归遍历该map；当元素count==0时说明该元素已遍历完。

void helper(map<int, int>& nums_count, int length, vector<int>& cur, vector<vector<int>>& ret){
      if(cur.size()==length){
          ret.push_back(cur);
          return;
     }
     for(auto iter=map.begin(); iter!=map.end(); iter++){
          if(iter->second==0)
              continue;
          iter->second--;
          cur.push_back(iter->first);
          helper(nums_count, length, cur, ret);
          iter->second++;
          cur.pop_back();
     }
}
vector<vector<int>> permuteUnique(vector<int>& nums){
     vector<vector<int>> ret;
     if(nums.size()==0)
           return ret;

    map<int, int> nums_count;
    for(auto val : nums){
         nums_count[val]++;
    }

    vector<int> cur;
    helper(nums_count, nums.size(), cur, ret);
    return ret;
}