聖地亞歌

Leetcode P0090"Subsets II" 题解

2020/08/31 Leetcode

博文中会简要介绍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],
  []
]
Plaintext

基本思路同样是每次枚举的子集大小，从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);
        }
    }
}
Java

以下是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();
        }
    }
};
C++

Search