Share my BFS solution and want to hear your advice on improvement.


  • 0
    Y
    vector < vector < int > > combine(int n, int k) {
    	vector < vector < int > > res;
    
    	queue < vector < int > > BFS;
    
    	for (int i=1; i<=n; ++i)
    	{
    		vector < int > tmp(1, i);
    		BFS.push(tmp);
    	}
    
    	while (!BFS.empty())
    	{
    		vector < int > work = BFS.front();
    		BFS.pop();
    		if (work.size() == k)
    		{
    			res.push_back(work);
    			continue;
    		}
    
    		if (work.size() < k)
    		{
    			int max = work.back();
    			if (max < n)
    			{
    				for (int i=max+1; i<=n; ++i)
    				{
    					vector < int > tmp(work);
    					tmp.push_back(i);
    					BFS.push(tmp);
    				}
    			}
    		}
    	}
    
    	return res;
    }

Log in to reply
 

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