[数据结构与算法] C++刷题之旅（56）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> C++刷题之旅（56） -> 正文阅读

[数据结构与算法]C++刷题之旅（56）

LeetCode算法入门（第五十六天）

递归/回溯

78.子集

在这里插入图片描述

class Solution {
public:
    vector<vector<int>> result;
    vector<int> ans;

    void backtracking(vector<int>& nums, int starIndex){
        result.push_back(ans);
        //因为子集是无序的，{1,2}与{2，1}是一样的，所以取过的元素不能重复取，故for循环从startIndex开始，而不是0
        for(int i = starIndex; i < nums.size(); i++){
            ans.push_back(nums[i]);  //处理节点，收集元素
            backtracking(nums, i + 1);  //递归， 从i+1开始，元素不重复取
            ans.pop_back();   //回溯
        }
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        result.clear();
        ans.clear();
        backtracking(nums, 0);
        return result;
    }
};

90.子集Ⅱ

在这里插入图片描述
本题与上一题的区别是，给定的数组中可能有重复元素，但是解集里不能有重复的解集，例如{1，2，2} 第一步取nums[0] = 1，第二步取nums[1] = 2后，第三步可以取nums[2] = 2，但是当回溯到重新取第二步的值时，由于前面已经取过nums[1] = 2，故本次不能再取nums[2] = 2。用unordered_set存储已经去到的元素，在回溯后需要取元素时判断是否已经取过相同的值。

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;

    void bracktracking(vector<int>& nums, int startIndex){
        result.push_back(path);
        unordered_set<int> uset;
        for(int i = startIndex; i < nums.size(); i++){
            //对同一层使用过的元素进行跳过
            if(uset.find(nums[i]) != uset.end()){
                continue;  //跳出本次循环
            }
            uset.insert(nums[i]);
            path.push_back(nums[i]);
            bracktracking(nums, i+1);
            path.pop_back();    //回溯
        }
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        path.clear();
        result.clear();
        sort(nums.begin(), nums.end());  //去重需要排序
        bracktracking(nums, 0);
        return result;
    }
};