[LeetCode] 90. Subsets II

轉自LeetCode

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

<Solution>

這題是 Subset 的衍生題，這次會有重複的數字出現，但最後的答案不能有重複的 subset

根據之前 DFS 的基礎，配合 set 來濾掉重複的 subset

以及因為要讓 set 能濾掉重複的 subset，在進行 DFS 之前，先對 nums 進行一次 sort

code 如下
c++

	class Solution {
	private:
	vector<int> out;
	vector<vector<int>> ans;
	public:
	vector<vector<int>> subsetsWithDup(vector<int>& nums) {
	ans.push_back(out);
	if(nums.empty()) {
	return ans;
	}
	set<vector<int>> outSet;
	//> sort first
	sort(nums.begin(), nums.end());
	for(int k = 1; k <= nums.size(); k++) {
	out.resize(k);
	dfs(0, 0, k, outSet, nums);
	}
	return ans;
	}
	void dfs(const int &start, const int &len, const int &targetLen, set<vector<int>> &outSet, vector<int>& nums) {
	if(len == targetLen) {
	//> not duplicates
	if(!outSet.count(out)) {
	outSet.insert(out);
	ans.push_back(out);
	}
	return;
	}
	for(int i = start; i < nums.size(); i++) {
	out[len] = nums[i];
	dfs(i+1, len+1, targetLen, outSet, nums);
	}
	}
	};

view raw findSubsetsII_1.cpp hosted with ❤ by GitHub

Kotlin

	class Solution {
	val ans = mutableListOf<List<Int>>()
	fun subsetsWithDup(nums: IntArray): List<List<Int>> {
	nums.sort()
	dfs(0, nums, emptyList())
	return ans
	}
	fun dfs(start: Int, nums: IntArray, cmb: List<Int>) {
	ans.add(cmb)
	val set = mutableSetOf<Int>()
	for(i in start..nums.lastIndex) {
	if(set.contains(nums[i])) {
	continue
	}
	set.add(nums[i])
	dfs(i+1, nums, cmb+listOf(nums[i]))
	}
	}
	}

view raw subsets_II.kt hosted with ❤ by GitHub

還有一種 iterative 的解法(參考資料)

想法如下

• 如果沒有重複數字，則每個數字就是要或不要兩種選擇。空集合代表的就是不要的選項，而要這個選項，就是把當前的數字放到之前所有的 subsets 中，形成新的 subsets

• 如果有重複數字，舉例有三個6，那麼會有 (3 + 1) 種狀況

• 全部都不放，也就是空集合的這個 subset

• 只放一個

• 只放兩個

• 全部放

所以，在放置數字來找到 subset 之前，先知道當前的數字有重覆幾次

這樣就可以用上面的邏輯，來找到所有 subsets

而為了能算出數字有重覆幾次，必須先對 nums 做一次 sort

code如下

C++

	class Solution {
	public:
	vector<vector<int>> subsetsWithDup(vector<int>& nums) {
	vector<vector<int>> ans = {{}};
	int index = 0, count;
	//> sort first
	sort(nums.begin(), nums.end());
	while(index < nums.size()) {
	//> count how many duplicates
	count = 1;
	while((index+count) < nums.size() && nums[index+count] == nums[index]) {
	++count;
	}
	//> put cuurent number into previous subsets to form new subsets
	int prvSize = ans.size();
	for(int j = 0; j < prvSize; j++) {
	vector<int> out = ans[j];
	for(int k = 0; k < count; k++) {
	out.push_back(nums[index]);
	ans.push_back(out);
	}
	}
	index += count;
	}
	return ans;
	}
	};

view raw findSubsetsII_2.cpp hosted with ❤ by GitHub

Java

	class Solution {
	public List<List<Integer>> subsetsWithDup(int[] nums) {
	List<List<Integer>> ans = new ArrayList<>();
	if(nums == null) {
	return ans;
	}
	ans.add(new ArrayList<Integer>());
	int index = 0, cnt, len;
	Arrays.sort(nums);
	while(index < nums.length) {
	cnt = 1;
	while((index+cnt) < nums.length && nums[index] == nums[index+cnt]) {
	++cnt;
	}
	len = ans.size();
	for(int i = 0; i < len; i++) {
	ArrayList<Integer> output = new ArrayList<>(ans.get(i));
	for(int j = 0; j < cnt; j++) {
	output.add(nums[index]);
	ans.add(new ArrayList<Integer>(output));
	}
	}
	index += cnt;
	}
	return ans;
	}
	}

view raw subsetsWithDup.java hosted with ❤ by GitHub