Разделение Равное Подмножество Сумма сверху вниз TLE - PullRequest
Новая
       8

Разделение Равное Подмножество Сумма сверху вниз TLE

0 голосов
/ 25 июня 2019

Я решаю Разделение равно подмножеству суммы кода leetcode.

Состояния проблемы: 

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

Each of the array element will not exceed 100.
The array size will not exceed 200.

Я написал код для следующего как 

class Solution {
public boolean canPartition(int[] nums) {
    int sum=0;
    for(int i=0;i<nums.length;i++)
    {
        sum=sum+nums[i];
    }
    if(sum%2!=0)
    {
        return false;
    }

    int target=sum/2;
    return helper(nums,target,nums.length);

}
boolean helper(int nums[],int sum,int n)
{
    if(sum==0)
    {
        return true;
    }
    if(sum<0)
    {
        return false;
    }
    if(n==0)
    {
        return false;
    }
    return helper(nums,sum-nums[n-1],n-1)||helper(nums,sum,n-1);
}


 }

Обратите внимание, что я не включил условие 

if(sum<nums[n-1])
{
return false;
}

в базовом случае, как я включил 

if(sum<0)
    {
        return false;
    }

Это то же самое, что просто добавить еще один рекурсивный вызов и затем вернуть false.

Этот код работает для 89 тестовых случаев, но выдает ошибку TLE для 

[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,100]

Теперь, если измените тот же код и включите 

if(sum<nums[n-1])
    {
    return false;
    }

и удалить 

if(sum<0)
    {
        return false;
    }

1028 * то есть * 

class Solution {
public boolean canPartition(int[] nums) {
    int sum=0;
    for(int i=0;i<nums.length;i++)
    {
        sum=sum+nums[i];
    }
    if(sum%2!=0)
    {
        return false;
    }

    int target=sum/2;
    return helper(nums,target,nums.length);

}
boolean helper(int nums[],int sum,int n)
{
    if(sum==0)
    {
        return true;
    }

    if(n==0)
    {
        return false;
    }
    if(nums[n-1]>sum)
    {
        return false;
    }

    return helper(nums,sum-nums[n-1],n-1)||helper(nums,sum,n-1);
}
}

Код работает нормально и проходит все тестовые случаи.

Поскольку оба кода одинаковы, как этот дополнительный рекурсивный вызов дает мне TLE? Есть что-то еще?

1 Ответ

0 голосов
/ 25 июня 2019

Тестовые случаи действительно слабые.Сначала нужно получить TLE, так как вы не использовали динамическое программирование, но выполнили простой возврат.Второй должен получить WA.Если бы вы использовали мемоизацию, ваша сложность была бы O( totalSum * arraySize), но сложность вашего кода равна O (2 ^ arraySize).

Теперь обратите внимание, что у вас есть два варианта в каждом состоянии.Или вы выбираете элемент или нет.Даже если это условие истинно if(nums[n-1]>sum), второй вариант действителен - идти вперед, не выбирая предмет.Но ваш второй код игнорирует оба случая для этого условия, сокращая количество вызовов до точки, в которой ваше решение занимает менее 1 миллисекунды, что быстрее, чем большинство правильных решений.Поскольку не было встречных контрольных примеров для второго решения, оно прошло.

...