My iterative using STL and recursive cpp solutions


  • 0
    C

    STL iterative:

    class Solution {
    public:
    
        vector<vector<int>> combine(int n, int k) 
        {
            vector< vector<int> > result;
            
            vector<char> perm(n, 0);
            for(int i = 0; i < k; i++)
                perm[perm.size()-1 - i] = 1;
                
            do
            {
                vector<int> solution;
                
                for(int i=0; i<n; i++)
                    if(perm[i]) 
                        solution.push_back(i+1);
                    
                result.push_back(solution);
                
            } while( std::next_permutation( perm.begin(), perm.end() ) );
            
            return result;
        }
    };
    

    Recursive:

    class Solution {
    public:
    
       	vector< vector<int> > result;
    
        void helper(int cur, vector<int> &res, int k, int n)
        {
        	if (!k)
        	{
        		result.push_back(res);
        		return;
        	}
        
        	if(cur > n) return;
        
        	int depth = res.size() - k;
        
        	// not choose cur
        	helper(cur + 1, res, k, n);
        
        	// choose cur
        	res[depth] = cur;
        	helper(cur + 1, res, k - 1, n);
        }
        
        vector<vector<int>> combine(int n, int k)
        {
            // c(i...j, k) = {i, c(i+1...j, k-1)} + c(i+1...j, k)
    
        	vector<int> res(k);
        	helper(1, res, k, n);
        
        	return result;
        }
    };

Log in to reply
 

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