Accepted 10ms c++ solution use backtracking, only 10 lines, easy understand.


  • 68

    The characteristics of C++ reference is an outstanding tool for backtracking algorithm!

    let us use [1,2,3,4] as an example to explain my solution:

    subsets([1,2,3,4]) = []
                         // push(1)
                         [1, subsets([2,3,4])] // if push N times in subsets([2,3,4]), the pop times is also N, so vec is also [1] after backtrack.
                         // pop(), push(2)
                         [2, subsets([3,4])]
                         // pop(), push(3)
                         [3, subsets([4])]
                         // pop(), push(4)
                         [4, subsets([])]
                         // pop()
    

    Accepted 10ms c++ solution use backtracking for Subsets

    class Solution {
    public:
        std::vector<std::vector<int> > subsets(std::vector<int> &nums) {
    		std::sort(nums.begin(), nums.end());
            std::vector<std::vector<int> > res;
    		std::vector<int> vec;
    		subsets(res, nums, vec, 0);
    		return res;
        }
    private:
    	void subsets(std::vector<std::vector<int> > &res, std::vector<int> &nums, std::vector<int> &vec, int begin) {
    		res.push_back(vec);
    		for (int i = begin; i != nums.size(); ++i) {
    			vec.push_back(nums[i]);
    			subsets(res, nums, vec, i + 1);
    			vec.pop_back();
    		}
    	}
    };
    

    Accepted 10ms c++ solution use backtracking for Subsets II

    class Solution {
    public:
        std::vector<std::vector<int> > subsetsWithDup(std::vector<int> &nums) {
    		std::sort(nums.begin(), nums.end());
            std::vector<std::vector<int> > res;
    		std::vector<int> vec;
    		subsetsWithDup(res, nums, vec, 0);
    		return res;
        }
    private:
    	void subsetsWithDup(std::vector<std::vector<int> > &res, std::vector<int> &nums, std::vector<int> &vec, int begin) {
    		res.push_back(vec);
    		for (int i = begin; i != nums.size(); ++i)
    			if (i == begin || nums[i] != nums[i - 1]) { 
    				vec.push_back(nums[i]);
    				subsetsWithDup(res, nums, vec, i + 1);
    				vec.pop_back();
    			}
    	}
    };
    

  • 8
    R

    Good explanation, and share my iterative method:

     vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> ret;
        ret.push_back(vector<int>());
        sort(nums.begin(), nums.end());
        vector<vector<int>> sub;
        for (int i = 0; i < nums.size(); ++i) {
            if (i == 0 || nums[i] != nums[i-1]) sub = ret;
            for (auto& j:sub) j.push_back(nums[i]);
            ret.insert(ret.end(), sub.begin(), sub.end());
        }
        return ret;
    }

  • 3
    P

    I love your solution, though mine is a little different.

    void subsetsWithDup(vector<int>& nums, vector<int> res, vector<vector<int>>& ans, int start) {
        if (start == nums.size()) {
            ans.push_back(res);
            return;
        }
        subsetsWithDup(nums,res,ans,start+1);
        while (start + 1 < nums.size() && nums[start] == nums[start+1]) {
            res.push_back(nums[start]);
            ++start;
        }
        res.push_back(nums[start]);
        subsetsWithDup(nums,res,ans,start+1);
    }
    
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<int> res;
        vector<vector<int>> ans;
        sort(nums.begin(),nums.end());
        subsetsWithDup(nums,res,ans,0);
        return ans;
    }

  • 0
    R

    what's the time complexity of your code ?


  • 0

    I think it is O(2^n), you can calculate the total push times as follow:

    t(0) = 0
    t(1) = 1+t(0)
    t(2) = 2+t(1)+t(0)
    ...
    t(n-1) = n-1+t(n-2)+t(n-3)+...+t(1)+t(0)
    t(n) = n+t(n-1)+t(n-2)+...+t(1)+t(0) = n+t(n-1)+t(n-1)-n+1=2t(n-1)+1
    
    => t(n)+1 = 2(t(n-1)+1) => t(n)+1 = 2^n => t(n) = 2^n-1

  • 0
    M

    Upvoted. This is the solution I am looking for, which is consistent with the approach -- "for each index, pick, or not".


  • 0
    E

    My first solution for subset I & II is a little different but also straightforward:

    1. subsetsWithDup([A, B]) = SubsetsWithDup(subsetsWithDup([A]), subsetsWithDup([B]))
    2. subsetsWithDup([A]) where A contains same number [A]=[a,a,...], is easy to find the solution:[],[a],[a,a],[a,a,a]...
    class Solution {
    private:
        void subsetAux(vector<int> & nums, vector<vector<int>>& res, vector<int>& subset, int begin) {
            if(begin==nums.size()) {
                res.push_back(subset);
                return;
            }
            int numSam = 1;
            while(begin+numSam<nums.size()&&nums[begin+numSam]==nums[begin]) numSam++;
            for(int i=0;i<=numSam;i++) {
                for(int j=0;j<i;j++) {
                    subset.push_back(nums[begin]);
                }
                subsetAux(nums, res, subset, begin+numSam);
                for(int j=0;j<i;j++) {
                    subset.pop_back();
                }
            }
        }
    public:
        vector<vector<int>> subsetsWithDup(vector<int>& nums) {
            sort(nums.begin(),nums.end());
            vector<vector<int>> res;
            vector<int> subset;
            subsetAux(nums, res, subset, 0);
            return res;
        }
    };
    

  • 0
    T

    @Ervine i m beginner in c++. I am trying to understand since ur function is a recursive function, where is the return in it ?


Log in to reply
 

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