leetcode题解-78-子集

发表于 | 更新于

题目

回溯法

递归实现

额外空间：\(O(n)\)

时间：\(O(2^n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
private:
    vector<vector<int>> sub;
public:
    void findSub(vector<int>& nums, vector<int>& tmp, const int pos)
    {
        if (pos >= nums.size())
        {
            sub.emplace_back(tmp);
            return ;
        }

        // add this element
        tmp.emplace_back(nums[pos]);
        findSub(nums, tmp, pos + 1);

        // not add this element
        tmp.pop_back();
        findSub(nums, tmp, pos + 1);
    }
    
    vector<vector<int>> subsets(vector<int>& nums) 
    {
        vector<int> tmp{};
        findSub(nums, tmp, 0);
        return sub;
    }
};

总结

  • 使用emplace_back() 而不是 push_back()

  • 我的理解：带有条件判断的DFS

    回溯法=>递归实现=>自动调栈<=> DFS

References

push_back vs emplace_back

Examples where std::vector::emplace_back is slower than std::vector::push_back?

push_back vs emplace_back to a std::vector