博文中会简要介绍Leetcode P0090题目分析及解题思路。
“Subsets II”是一道p0078变形题，也是深度优先搜索的问题。
Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: [1,2,2] Output: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
基本思路同样是每次枚举的子集大小，从0开始到n结束，针对每个给定的子集大小，深度优先搜索得到所有该大小的子集。需要注意的是，由于有重复元素，需要跳过那些重复元素的副本。
不难发现，类似这样的深度优先搜索问题，分成四大类，一种是纯粹递归问题，一种是探索问题，即判断合法性等，后两种分别是寻找组合和寻找排列。而寻找组合往往涉及到去重，并且每次以新元素作为探索起点时，前面探索中访问过的起点不再访问。寻找排列除了去重以外，每次以新元素作为探索起点时，在前面探索中访问过的起点，还可以继续访问。
以下是Java的题解代码实现。
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
for (int size=0; size<=nums.length; ++size) {
this.dfs(size, nums, 0, new ArrayList<>());
}
return this.subsets;
}
private List<List<Integer>> subsets = new ArrayList<>();
private void dfs(int size, int[] nums, int start, List<Integer> subset) {
if (size <= 0) {
this.subsets.add(new ArrayList<>(subset));
return;
}
int len = nums.length;
for (int itr=start; itr<len; ++itr) {
// 或者当前元素和前一个元素一致，说明需要去重，跳过
if (itr > start && nums[itr] == nums[itr-1])
continue;
subset.add(nums[itr]);
this.dfs(size-1, nums, itr+1, subset);
subset.remove(subset.size()-1);
}
}
}
以下是C++的题解代码实现。
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
for (int size=0; size<=nums.size(); ++size) {
vector<int> subset;
this->Dfs(size, nums, subset, 0);
}
return this->subsets;
}
private:
vector<vector<int>> subsets;
void Dfs(int size, vector<int> &nums, vector<int> &subset, int start) {
if (size <= 0) {
this->subsets.push_back(vector<int>(subset));
return;
}
int len = nums.size();
for (int itr=start; itr<len; ++itr) {
if (itr > start && nums[itr] == nums[itr-1])
continue;
subset.push_back(nums[itr]);
this->Dfs(size-1, nums, subset, itr+1);
subset.pop_back();
}
}
};