Share My C++ backtracksolution


  • 7
    A
    class Solution {
    public:
        vector<vector<int> > permute(vector<int> &num) {
        	vector<vector<int> > res;   // result
        	vector<bool> flags( num.size(), false);    // bool, whether num[i] is choosed
        	vector<int> path;     // num have been choosed
        	backtrack(num, res, path, flags);   //backtrack
        	return res;	
        }
    
        void backtrack(vector<int> &num, vector<vector<int> > &res, 
    	vector<int> path,vector<bool> flags)
    {
    	if( num.size() == path.size() )
    	{
    		res.push_back(path);
    	}
    	else
    	{
    		for( int i = 0; i < num.size(); i++ )
    		{
    			if( flags[i] == true )
    				continue;
    			else
    			{
    				path.push_back(num[i]);
    				flags[i] = true;
    				backtrack( num, res, path, flags );
    				flags[i] = false;
    				path.pop_back();
    			}
    			
    		}
    	}
    
    }

Log in to reply
 

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