Why does sorting in decreasing order reduce the complexity so drastically?


  • 0
    S

    1025 ms

    class Solution {
    public:
        int n ;
        bool solve( int pos , long long int a , long long int b , long long int c , long long int d , vector <int> & nums )
        {
            if( pos == n )
                return !a && !b && !c &&!d ;
            bool res = false ;
            if( nums[pos] <= a )
                res |= solve( pos + 1 , a - nums[pos] , b , c , d , nums ) ;
            if( !res && nums[pos] <= b )
                res |= solve( pos + 1 , a , b - nums[pos] , c , d , nums ) ;
            if( !res && nums[pos] <= c )
                res |= solve( pos + 1 , a , b , c - nums[pos] , d , nums ) ;
            if( !res && nums[pos] <= d )
                res |= solve( pos + 1 , a , b , c , d - nums[pos] , nums ) ;
            return res ;
        }
        bool makesquare(vector<int>& nums) {
            int i ;
            n = nums.size( ) ;
            if( !n )
                return false ;
            long long int sum = 0 ;
            for( i = 0 ; i < n ; i++ )
                sum += nums[i] ;
            if( sum % 4 )
                return false ;
            sum /= 4 ;
            
            return solve( 0 , sum , sum , sum , sum , nums ) ;
        }
    };
    

    19 ms

    bool cmp( int a , int b )
    {
        return a > b ;
    }
    class Solution {
    public:
        int n ;
        bool solve( int pos , long long int a , long long int b , long long int c , long long int d , vector <int> & nums )
        {
            if( pos == n )
                return !a && !b && !c &&!d ;
            bool res = false ;
            if( nums[pos] <= a )
                res |= solve( pos + 1 , a - nums[pos] , b , c , d , nums ) ;
            if( !res && nums[pos] <= b )
                res |= solve( pos + 1 , a , b - nums[pos] , c , d , nums ) ;
            if( !res && nums[pos] <= c )
                res |= solve( pos + 1 , a , b , c - nums[pos] , d , nums ) ;
            if( !res && nums[pos] <= d )
                res |= solve( pos + 1 , a , b , c , d - nums[pos] , nums ) ;
            return res ;
        }
        bool makesquare(vector<int>& nums) {
            int i ;
            //Extra
            sort( nums.begin( ) , nums.end( ) , cmp ) ;
            n = nums.size( ) ;
            if( !n )
                return false ;
            long long int sum = 0 ;
            for( i = 0 ; i < n ; i++ )
                sum += nums[i] ;
            if( sum % 4 )
                return false ;
            sum /= 4 ;
            
            return solve( 0 , sum , sum , sum , sum , nums ) ;
        }
    };
    

Log in to reply
 

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