[LeetCode] 47. Permutations II

轉自LeetCode

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

<Solution>

Permutations 的衍生題，差別在於可能會有重複的數字

最簡單的解法，還是使用 next_permutation，而且速度還很快 (30/30 test cases, 23ms, 86.19%)

code 如下

	class Solution {
	public:
	vector<vector<int>> permuteUnique(vector<int>& nums) {
	vector<vector<int>> ans;
	sort(nums.begin(), nums.end());
	do {
	ans.push_back(nums);
	} while(next_permutation(nums.begin(), nums.end()));
	return ans;
	}
	};

view raw permutateUnique_1.cpp hosted with ❤ by GitHub

那當然也可以用 DFS 來解，只是要修改一下

• 用 set 來濾掉重複的答案

• 不用去 swap 同樣數值的位置

光用 set 其實就可以得到正解，不去 swap 同樣數值，是用來加速的

code 如下
c++

	class Solution {
	public:
	vector<vector<int>> permuteUnique(vector<int>& nums) {
	//> use set to avoid duplicates
	set<vector<int>> out;
	permuteDFS(0, nums, out);
	return vector<vector<int>> (out.begin(), out.end());
	}
	void permuteDFS(const int &start, vector<int>& nums, set<vector<int>> &out) {
	if(start == nums.size()) {
	out.insert(nums);
	return;
	}
	for(int i = start; i < nums.size(); i++) {
	if(i != start && nums[i] == nums[start]) {
	//> no need to swap same value
	continue;
	}
	else {
	swap(nums[start], nums[i]);
	permuteDFS(start+1, nums, out);
	swap(nums[start], nums[i]);
	}
	}
	}
	};

view raw permueateUnique_2.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	val ans = mutableSetOf<List<Int>>()
	fun permuteUnique(nums: IntArray): List<List<Int>> {
	dfs(0, nums, emptyList())
	return ans.toList()
	}
	private fun dfs(start: Int, nums: IntArray, cmb: List<Int>) {
	if (start == nums.size) {
	ans.add(cmb)
	}
	for (i in start until nums.size) {
	if (i > start && nums[i] == nums[start]) {
	continue
	}
	nums[start] = nums[i].also { nums[i] = nums[start] }
	dfs(start+1, nums, cmb+nums[start])
	nums[start] = nums[i].also { nums[i] = nums[start] }
	}
	}
	}

view raw permutationsII.kt hosted with ❤ by GitHub