Subsets and Subsets II (回溯，DFS，组合问题)-白红宇

Subsets and Subsets II (回溯，DFS，组合问题)

阅读量：6157 次

发布时间：2019-06-21

本文共 1477 字，大约阅读时间需要 4 分钟。

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],  []] 该题和很类似，只不过是k需要从0到size中取值。

class Solution {private:    vector
     
      
       > res;    vector
       
         s;public:    void tra(int k,int start,int dep,vector
        
          temp)    {        if(dep==k){            res.push_back(temp);            return;        }        for(int i=start;i

> subsets(vector

&S) { s=S; sort(s.begin(),s.end()); vector

temp; for(int k=0;k<=s.size();++k){ tra(k,0,0,temp); } return res; }};

我的分析图：

Subsets 2

Given a collection of integers that might contain duplicates, 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,2], a solution is:

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

class Solution {private:    vector
     
      
       > res;    vector
       
         s;public:    void tra(int k,int start,int dep,vector
        
          temp)    {        if(dep==k){            for (int i=0;i

> subsetsWithDup(vector

&S) { s=S; sort(s.begin(),s.end()); vector

temp; res.push_back(temp); for(int k=1;k<=s.size();++k){ tra(k,0,0,temp); } return res; }};

转载于:https://www.cnblogs.com/fightformylife/p/4118071.html