博文中会简要介绍Leetcode P0047题目分析及解题思路。
“Permutations II”是p0046的变形题，题目中的数组从原先的无重复元素到现在有重复元素。解题思路基本不变，但是如何去重是重点。
Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
这里讲解一下这道题的去重思路。首先对数组进行排序，则重复元素会连续排列。其次维护一个used数组代表已经访问过的元素，此时如果迭代的指针itr前面一个元素没有被访问但是前面一个元素和当前元素相同，则跳过当前元素。原因很简单，因为我们的访问是顺序访问从左到右，所以如果左边没有访问，且当前元素和左边相同，则说明左边元素是在上一轮被访问的元素，是在上一轮探索中被放在位置k的元素，而此时当前元素如果继续放在位置k则显然会造成重复，所以跳过去重。
以下是Java的题解代码实现。
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
this.dfs(nums, new ArrayList<>(), new boolean[nums.length], 0);
return this.permutations;
}
private List<List<Integer>> permutations = new ArrayList<>();
private void dfs(int[] nums, List<Integer> sequence, boolean[] used, int count) {
if (count >= nums.length) {
List<Integer> copied = new ArrayList<>(sequence);
this.permutations.add(copied);
return;
}
for (int itr=0; itr<nums.length; ++itr) {
// 去重
if (used[itr] || (itr > 0 && !used[itr-1] && nums[itr] == nums[itr-1]))
continue;
used[itr] = true;
sequence.add(nums[itr]);
this.dfs(nums, sequence, used, count+1);
sequence.remove(sequence.size()-1);
used[itr] = false;
}
}
}
以下是C++的题解代码实现。
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<bool> used(nums.size(), false);
vector<int> sequence;
this->dfs(nums, used, sequence, 0);
return this->permutations;
}
private:
vector<vector<int>> permutations;
void dfs(vector<int> &nums, vector<bool> &used, vector<int> &sequence, int count) {
if (count >= nums.size()) {
vector<int> copied(sequence);
this->permutations.push_back(copied);
return;
}
for (int itr=0; itr<nums.size(); ++itr) {
if (used[itr]
|| (itr > 0 && !used[itr-1] && nums[itr] == nums[itr-1]))
continue;
used[itr] = true;
sequence.push_back(nums[itr]);
this->dfs(nums, used, sequence, count+1);
sequence.pop_back();
used[itr] = false;
}
}
};