Accepted : Dynamic Solution with explanation in cpp


  • 7
    L
    /*
       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;
        }

  • 1
    D

    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


Log in to reply
 

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