leetcode 90. Subsets II DFS深度优先搜索 + 全排列

我就是我 2022-06-08 02:35 200阅读 0赞

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\],  
\[\]  
\]

这道题很简单，不过就是把重复的子集给去掉。

建议和这一道题[leetcode 78. Subsets DFS深度优先搜索][leetcode 78. Subsets DFS] 和[leetcode 77. Combinations 按照index递归搜索+全排列做法][leetcode 77. Combinations _index]一起学习

代码如下：

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class Solution 
    {
        List<List<Integer>> res=new ArrayList<>();
        public List<List<Integer>> subsetsWithDup(int[] nums) 
        {
            if(nums==null || nums.length<=0)
            {
                res.add(new ArrayList<>());
                return res;
            }
            Arrays.sort(nums);
            List<Integer> one=new ArrayList<>();
            getFullPute(nums,one,0);
            return res;
        }
    
    
        private void getFullPute(int[] nums, List<Integer> one, int i)
        {
            if(i==nums.length)
            {
                boolean need=true;
                for(int k=0;k<res.size();k++)
                {
                    if(res.get(k).size()==one.size())
                    {
                        need=false;
                        break;
                    }
                }
                if(need)
                    res.add(new ArrayList<>(one));
                else
                {
                    need =true;
                    for(int k=0;k<res.size();k++)
                    {
                        List<Integer> tmp=res.get(k);
                        if(tmp.size()==one.size())
                        {
                            int j=0;
                            for(;j<tmp.size();j++)
                            {
                                if(tmp.get(j)!=one.get(j))
                                    break;
                            }
                            if(j==tmp.size())
                            {
                                need=false;
                                break;
                            }
                        }
                    }
                    if(need)
                        res.add(new ArrayList<>(one));
                }
    
            }else
            {
                //不选择当前的元素的处理
                getFullPute(nums, one, i+1);    
                //选择当前元素的处理
                one.add(nums[i]);
                getFullPute(nums, one, i+1);
                one.remove(one.size()-1);
            }   
        }
    }

下面是C++的做法，和上一道题一样，就是一个DFS深度优先遍历的应用做法

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    
    
    class Solution
    {
    public:
        set<vector<int>> res;
        vector<vector<int>> subsetsWithDup(vector<int>& a)
        {
            sort(a.begin(), a.end());
            dfs(0, vector<int>(), a);
            return vector<vector<int>>(res.begin(),res.end());
        }
    
        void dfs(int k, vector<int> one, vector<int> a)
        {
            if (k == a.size())
                res.insert(one);
            else
            {
                dfs(k + 1, one, a);
    
                one.push_back(a[k]);
                dfs(k + 1, one, a);
                one.pop_back();
            }
        }
    };

[leetcode 78. Subsets DFS]: http://blog.csdn.net/jackzhang_123/article/details/77938096
[leetcode 77. Combinations _index]: http://blog.csdn.net/jackzhang_123/article/details/77938048