回溯算法|90.子集II

力扣题目链接

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIndex, vector<bool>& used) {
        result.push_back(path);
        for (int i = startIndex; i < nums.size(); i++) {
            // used[i - 1] == true,说明同一树枝candidates[i - 1]使用过
            // used[i - 1] == false,说明同一树层candidates[i - 1]使用过
            // 而我们要对同一树层使用过的元素进行跳过
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            path.push_back(nums[i]);
            used[i] = true;
            backtracking(nums, i + 1, used);
            used[i] = false;
            path.pop_back();
        }
    }

public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        result.clear();
        path.clear();
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end()); // 去重需要排序
        backtracking(nums, 0, used);
        return result;
    }
};

40.组合总和II

可以顺便复习一下这题,如何去重?

因为自己没完全搞懂40题,所以独自写下来,关于去重部分那点始终没想到。

 

思路

做本题之前一定要先做78.子集 (opens new window)

这道题目和78.子集 (opens new window)区别就是集合里有重复元素了,而且求取的子集要去重。

那么关于回溯算法中的去重问题,40.组合总和II (opens new window)中已经详细讲解过了,和本题是一个套路

剧透一下,后期要讲解的排列问题里去重也是这个套路,所以理解“树层去重”和“树枝去重”非常重要

用示例中的[1, 2, 2] 来举例,如图所示: (注意去重需要先对集合排序

从图中可以看出,同一树层上重复取2 就要过滤掉,同一树枝上就可以重复取2,因为同一树枝上元素的集合才是唯一子集!

本题就是其实就是回溯算法:求子集问题! (opens new window)的基础上加上了去重,去重我们在回溯算法:求组合总和(三) (opens new window)也讲过了

一起复习复习下咯!记住used的使用~

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-04-02 18:38:02       142 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-04-02 18:38:02       156 阅读
  3. 在Django里面运行非项目文件

    2024-04-02 18:38:02       131 阅读
  4. Python语言-面向对象

    2024-04-02 18:38:02       141 阅读

热门阅读

  1. 冥想第一千一百一十七天

    2024-04-02 18:38:02       46 阅读
  2. 在linux上设置nginx上自动启动

    2024-04-02 18:38:02       42 阅读
  3. 第一章设计模式概述

    2024-04-02 18:38:02       45 阅读
  4. 介绍几个AI相关的工具

    2024-04-02 18:38:02       56 阅读
  5. 【软考高项范文】论信息系统项目的进度管理

    2024-04-02 18:38:02       36 阅读
  6. WebRTC即时通讯核心协议-TRUN(RFC5766)

    2024-04-02 18:38:02       33 阅读
  7. 队列的顺序实现

    2024-04-02 18:38:02       44 阅读
  8. 松鼠症患者福音-视频下载工具

    2024-04-02 18:38:02       37 阅读
  9. set的一些用法和问题

    2024-04-02 18:38:02       52 阅读
  10. 【Tomcat】Apache Tomcat 8.5正式结束官方支持

    2024-04-02 18:38:02       43 阅读
  11. macad.interaction解析liveactions、panels

    2024-04-02 18:38:02       37 阅读
  12. 从唯一序列码、单例模式到集群的思考

    2024-04-02 18:38:02       43 阅读