8ms c++ solution using recursion


  • 0
    L

    It feels like that many similar problems can be solved using this recursion and backtracking way.

    class Solution {
    public:
    	void helper(int start, int end, int size, vector<vector<int> >& ret, vector<int>& comb)
    	{
    		comb.push_back(start);
    		if(comb.size() == size) // if comb's size equals k, add comb into ret;
    			ret.push_back(comb);
    		else // if not, get (size - comb.size()) more number from range [start+1, n];
    			for(int i = start+1; i <= end; i++)
    				helper(i, end, size, ret, comb);
    		comb.pop_back(); // key part, comb.back() must have been added into ret, so delete it.
    	}
    
        vector<vector<int> > combine(int n, int k) {
            vector<vector<int> > all;
        	if(k <= 0 || n <= 0 || k > n)
        		return all;
        	vector<int> one;
            // get k numbers from range i to n, where i is from 1 to n;
        	for(int i = 1; i <= n - k + 1; i++)
        		helper(i, n, k, all, one);
        	return all;
        }
    };

Log in to reply
 

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