Subsets and Subsets II both problems simple backtracking approch


  • 0
    R

    Subsets

    void subsetHelper(vector<int>& nums,vector<vector<int>> &res, vector<int>& subset ,int start ){
            res.push_back(subset);
            for(int i=start ; i<nums.size() ; i++){
            subset.push_back(nums[i]);          // put the current element in subset 
            subsetHelper(nums,res,subset,i+1);  // call with next element in nums at index i+1
            subset.pop_back();                        // backtrack setp     
            }
        }
        vector<vector<int>> subsets(vector<int>& nums) {
              vector<vector<int>> res;
            vector<int>subset;
            subsetHelper(nums,res,subset,0);
            return res;
        }
    

    Subsets II

       void subsetHelper(vector<int>& nums,vector<vector<int>> &res, vector<int>& subset ,int start ){
            res.push_back(subset);
            for(int i=start ; i<nums.size() ; i++){
           
               if(i==start || nums[i]!=nums[i-1]){  
                  subset.push_back(nums[i]);        // put the current element in subset    
                  subsetHelper(nums,res,subset,i+1);   // call with next element in nums at index i+1
                  subset.pop_back();        // call with next element in nums at index i+1
    	     }
            }
        }
        vector<vector<int>> subsetsWithDup(vector<int>& nums) {
            vector<vector<int>> res;
            vector<int>subset;
            sort(nums.begin(),nums.end());
            subsetHelper(nums,res,subset,0);
            return res;
        }

Log in to reply
 

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