首页 > 代码库 > [leetcode] Subsets

[leetcode] Subsets

2024-10-26 05:41:02   206人阅读

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],  []]

思路：

dfs。原容器中的元素在子集中有两种可能，要么在要么不在。因此肯定在一个函数中有两个递归的过程，一个是不放数据，一个是放数据。如此一直递归，直到原容器的大小时递归结束。

题解：

技术分享
class Solution {public:    vector<vector<int> > res;    void dfs(vector<int> &s, int index, vector<int> tmp) {        if(index==s.size()) {            res.push_back(tmp);            return;        }        dfs(s, index+1, tmp);        tmp.push_back(s[index]);        dfs(s, index+1, tmp);    }    vector<vector<int> > subsets(vector<int> &s) {        sort(s.begin(), s.end());        vector<int> tmp;        dfs(s, 0, tmp);        return res;    }};
View Code

后话：

在Disuss中看到有人用动态规划来解这道题目，很不错的方法。暂时没理解，放着以后好好研究研究。

技术分享
 vector<vector<int> > subsets(vector<int> &S) {        vector <int> temp;        vector<vector<int> >ans;        ans.push_back(temp);   //Enters null set        int len=S.size();        int len2;        if(len==0)         return ans;        sort(S.begin(),S.end());        for(int i=0 ; i<len ; i++)   //Traverses the whole input array        {                len2=ans.size();          // Since we cannot append the new number along with the null set therefore this is done outside the loop            temp.clear();            temp.push_back(S[i]);            ans.push_back(temp);            for(int j=1 ; j<len2 ; j++)            {                vector<int> temp2(ans[j]);                temp2.push_back(S[i]);                ans.push_back(temp2);            }        }        return ans;    }
View Code

 

[leetcode] Subsets


联系
我们