`
SunnyYoona
  • 浏览: 361514 次
社区版块
存档分类
最新评论

[LeetCode]78.Subsets

 
阅读更多

题目

Given a set of distinct integers, S, return all possible subsets.

Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If S = [1,2,3], a solution is:

[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

分析

充分利用[LeetCode]77.Combinations
本题其实对上题的拓展,上题是一种长度的组合,本题则是穷尽不同长度的组合。
假设S长度为Len,则令 0 <= K <= Len

代码

    /**------------------------------------
    *   日期:2015-02-06
    *   作者:SJF0115
    *   题目: 78.Subsets
    *   网址:https://oj.leetcode.com/problems/subsets/
    *   结果:AC
    *   来源:LeetCode
    *   博客:
    ---------------------------------------**/
    #include <iostream>
    #include <cstring>
    #include <vector>
    #include <algorithm>
    using namespace std;

    class Solution {
    public:
        vector<vector<int> > subsets(vector<int> &S) {
            int size = S.size();
            vector<vector<int> > result;
            vector<int> path;
            // 排序
            sort(S.begin(),S.end());
            // 空集
            result.push_back(path);
            // 其他子集
            for(int i = 1;i <= size;++i){
                DFS(S,size,i,0,path,result);
            }//for
            return result;
        }
    private:
        void DFS(vector<int> &s,int n,int k,int index,vector<int> &path,vector<vector<int> > &result){
            // 一个子集
            if(path.size() == k){
                result.push_back(path);
                return;
            }//if
            for(int i = index;i < n;++i){
                path.push_back(s[i]);
                DFS(s,n,k,i+1,path,result);
                path.pop_back();
            }//for
        }
    };

    int main(){
        Solution s;
        vector<int> num = {4,3,2};
        vector<vector<int> > result = s.subsets(num);
        // 输出
        for(int i = 0;i < result.size();++i){
            for(int j = 0;j < result[i].size();++j){
                cout<<result[i][j]<<" ";
            }//for
            cout<<endl;
        }//for
        return 0;
    }

运行时间

这里写图片描述

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics