# Accepted : Dynamic Solution with explanation in cpp

• ``````/*
LEgend:
#S -> size of input set
#SS(n) -> total number of subsets for a set with size n (i.e 2^n)
S(i) ->ith element of input set
SS(i) -> ith element of the set of subsets of S (starting from 0)
SSn = set of Subset for Sn
SS(#SS(n)-1) -> Last element in SSn

Logic:
#SS(n)= 2 * #SS(n-1)
=> SSn = SSn-1 U { {SS(0),S(n)} , {SS(1),S(n)} , ...  , {SS(#SS(n-1)-1),S(n)} }

Explanation :
In simple words,I am using the logic of Dynamic Programming and breaking the problem in smaller subproblems

eg. S={1,2}
SS2 = { { } , {1} , {2} , {1,2} }

now to get the subset for {1,2,3} we add the element 3
in each of the solution set of SS and with this new set do union of SS

SS3 = SS2 U { {3} , {1,3} , {2,3} , {1,2,3} }
= { {} , {1} , {2} , {1,2} , {3} , {1,3} , {2,3} , {1,2,3} }
*/

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;
}``````

• Same idea with you !

`````` class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
vector<vector<int> > R;
R.push_back(vector<int>());
sort(S.begin(), S.end());
for (int i = 0; i<S.size(); i++)
{
int Rsize = R.size();
for (int j = 0; j<Rsize; j++)
{
vector<int> sub(R[j]);
sub.push_back(S[i]);
R.push_back(sub);
}
}
return R;
}
};
``````

And one more thing,
no need to check

``````if(len==0)
return ans;
``````

the loop `for(int i=0 ; i<len ; i++)`will stop if len==0

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.