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

• 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 ) ;
}
};
``````

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