【深度优先搜索】集合问题中去重问题的思考

解法参考：代码随想录

代码随想录

例题:

（1）给定一个数组，返回所有幂集（数组中有重复元素）

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

如：下标1的[2]和下标2的[2]是重复的，下标1的[1,2]和下标2的[1,2]是重复的.......

（2）给定一个数组，返回所有递增子序列（数组中有重复元素）

输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

（3）给定一个数组和一个目标数,找出数组中所有可以使数字和为 target 的组合。（数组中有重复元素）

题解：

【深度优先搜索】子集| &&子集||_暮色_年华的博客-CSDN博客

上面的题目具有一个特征，就是在同一个集合中可以重复，但是集合与集合中间不可以重复。

因为dfs可以对应一棵树，同一个集合对应一棵树从根节点到叶子节点的一条路径。

而不同的集合就对应一颗树相同的高度的所有路径。

如果在相同的高度有两条路径对应的集合是相同的，那么在进行下一步选的时候，这两个路径的选择是相同的，所以会有重复的情况。

dfs的模板：

dfs()
      
  for(所有选择):
    dfs();

 图示：

两种方法：

一：如果数组可以进行排序，那么可以用num[i]==num[i-1]来去重

如果num[i-1]和num[i]相等，那么在同一层中，这两个就是重复元素，只算一个即可。

二：在for循环前加set数组去重，如果已经选过，就直接跳过。

int used[];

for():

if(used[i])continue;

used[i]=1;

注意：used不需要回溯， 如果回溯，那么相当于没有标记。

在每一层的时候，used都需要进行一次初始化（memset），进行去重操作。

题解代码：

递增子序列：

class Solution {
public:
    vector>res;
    vectorpath;
    int n;
    vectora;
    void dfs(int index){
        if(path.size()>=2){
        res.push_back(path);
        int uset[201];
        memset(uset,0,sizeof(uset));
        for(int i=index;i0&&a[i]> findSubsequences(vector& nums) {
        a=nums;
        n=nums.size();
        dfs(0);
        return res;
    }
};

子集||

class Solution {
public:
    vector>res;
    vectorpath;
    vectora;
    int n;
    void dfs(int index){
        //每次做选择后都要计入res
        res.push_back(path);
        int uset[21];
        memset(uset,0,sizeof(uset));
    for(int i=index;i> subsetsWithDup(vector& nums) {
          a=nums;
          sort(a.begin(),a.end());
          n=nums.size();
          dfs(0);
          return res;
    }
};