leetcode78：子集

题目链接

leetcode

题目描述

给你一个整数数组 nums，数组中的元素互不相同，返回该数组所有可能的子集（幂集）。
解集不能包含重复的子集。可以按任意顺序返回解集。

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*
    回溯法，深度优先搜索

    一共枚举 n 层，
    start 表示当前数字从 nums[start] 开始选择，保证数字递增。

    时间复杂度：O(2^n*n)
        一共枚举 2^n 个数，每个数枚举 n 位。
        所以，时间复杂度是 O(2^n*n)。
    空间复杂度：O(n)
        递归的最大深度为数组的长度 n，空间复杂度为 O(n)。
        存储当前路径的 path 最多包含 n 个数字，空间复杂度为 O(n)。
*/
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        result.clear();
        path.clear();
        if (nums.empty()) {
            return {};
        }

        dfs(nums, 0);

        return result;
    }

    void dfs(vector<int>& nums, int start) {
        // // 结束条件：此处可以不加
        // if (start >= nums.size()) {
        //     return;
        // }
        // 将当前路径加入结果（包括空集）
        result.push_back(path);
        
        for (int i = start; i < nums.size(); i++) {
            path.push_back(nums[i]); // 选择
            dfs(nums, i + 1);        // 进入下一层决策树
            path.pop_back();         // 撤销选择（回溯）
        }
    }

private:
    vector<vector<int>> result; // 存放最终结果
    vector<int> path; // 存放当前路径
};

// 辅助函数：打印数组
void printArray(vector<int>& nums) {
	cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size()-1) {
            cout << ",";
        }
    }
    cout << "]" << endl;
}

// 辅助函数：打印二维数组
void printArray(const vector<vector<int>>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << "[";
        for (size_t j = 0; j < nums[i].size(); j++) {
            cout << nums[i][j];
            if (j != nums[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

int main() {
    Solution solution;
    vector<vector<int>> nums_cases = {
        {1,2,2},
        {0}
    };

    for (size_t i = 0; i < nums_cases.size(); i++) {
        auto& nums = nums_cases[i];
        cout << "Input: nums = ";
        printArray(nums);

        vector<vector<int>> result = solution.subsets(nums);
        cout << "Output: ";
        printArray(result);
    }
    
    return 0;
}