【LeetCode】47. Permutations II

2019-11-06 07:13:54

字体：大中小

来源：转载

供稿：网友

题目描述

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], [2,1,1]]

解题思路

回溯法。与46. Permutation差不多，只不过这里的元素是有重复的。先将元素排序，然后在for循环中，往后跳过与当前重复的所有元素即可。

AC代码

class Solution {public: void backtract(vector<vector<int>>& ans, vector<int>& cur, const vector<int>& nums, vector<bool>& isVisited) { if (cur.size() >= nums.size()) { ans.push_back(cur); return; } for (int i = 0; i < nums.size(); ++i) { if (!isVisited[i]) { isVisited[i] = true; cur.push_back(nums[i]); backtract(ans, cur, nums, isVisited); cur.pop_back(); isVisited[i] = false; int nextIdx = i; while(nextIdx < nums.size() && nums[nextIdx] == nums[i]) nextIdx++; i = nextIdx - 1; } } } vector<vector<int>> permuteUnique(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<vector<int>> ans; vector<int> cur; vector<bool> isVisited(nums.size(), false); backtract(ans, cur, nums, isVisited); return ans; }};

上一篇：top interview questions 2

下一篇：HashMap的put源码解析