Subsets

作者: 克罗地亚催眠曲 | 来源:发表于2018-08-14 15:08 被阅读8次

这是一道求子集的题目,题目链接,一开始用了三重循环,复杂度极高,不过还是没有超时。代码如下

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        set<set<int>> ans_s;
        ans_s.insert(set<int>({}));
        for(int i = 0; i <= nums.size(); i++){
            auto tmp = ans_s;
            for(auto num : nums){
                for(auto s_s : tmp){
                    s_s.insert(num);
                    ans_s.insert(s_s);
                }
            }
        }

        vector<vector<int>> ans;
        for(auto s : ans_s){
            ans.push_back(vector<int>(s.begin(), s.end()));
        }
        return ans;
    }
};

代码思路就是每次加入一个数字,得到当前的所有子集。直到所有数字都被加入。这中做法使用set来去除重复。
第二种的思路是用回溯的思想,参考了前一道题目的代码。代码如下

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        helper(nums, 0, vector<int>(), ans);
        return ans;
    }
    
    void helper(vector<int> &nums, int pos, vector<int> out, vector<vector<int>> &ans) {
        ans.push_back(out);
        for(int i = pos; i < nums.size(); ++i) {
            out.push_back(nums[i]);
            helper(nums, i+1, out, ans);
            out.pop_back();
        }
    }
};

相关文章

  • LeetCode #78 #90 2018-07-30

    78. Subsets https://leetcode.com/problems/subsets/descrip...

  • 78.Subsets

    78.Subsets 题目:https://leetcode.com/problems/subsets/ 难度 :...

  • Leetcode-backTracking

    Leetcode 78. Subsets. Subsets题,时间复杂度一般是O(2^n), 因为 2^n是子集的...

  • Subsets

    这是一道求子集的题目,题目链接,一开始用了三重循环,复杂度极高,不过还是没有超时。代码如下 代码思路就是每次加入一...

  • subSets

    题目 给定一个含不同整数的集合,返回其所有的子集(子集中的元素排列必须是非降序的,解集必须不包含重复的子集)如果 ...

  • Subsets

    Lintcode--Subsets Despriction Given a set of distinct int...

  • Subsets Ⅱ

    Despriction 给定一个可能具有重复数字的列表,返回其所有可能的子集 ** 注意事项** 子集中的每个元素...

  • Subsets

    //78. Subsets Given a set of distinct integers, nums, ret...

  • Subsets

    ===================== 解題思路 ===================== 用 backtr...

  • Subsets

    Given a set of distinct integers, nums, return all possib...

网友评论

      本文标题:Subsets

      本文链接:https://www.haomeiwen.com/subject/xokvbftx.html