Учитывая массив целых чисел и сумму, задача состоит в том, чтобы найти, существует ли подмножество данного массива с суммой, равной данной сумме - PullRequest
Новая
       80

Учитывая массив целых чисел и сумму, задача состоит в том, чтобы найти, существует ли подмножество данного массива с суммой, равной данной сумме

3 голосов
/ 19 марта 2020

Вот функция, которую я написал. 

    public static boolean existsSum(int[] arr, int n, int sum){
            if(sum==0)
                return true;
            if(n<=0)
                return false;
            if(arr[n-1] == sum)
                return true;
            if(sum<0)
                return false;
            if(sum<arr[n-1])
                return existsSum(arr, n-1,sum);
            return existsSum(arr, n-1, sum-arr[n-1])  || existsSum(arr, n-1,sum)  ;
        }

Это прекрасно работает. Но как только я изменяю последнюю строку кода, как это 

    public static boolean existsSum(int[] arr, int n, int sum){
            if(sum==0)
                return true;
            if(n<=0)
                return false;
            if(arr[n-1] == sum)
                return true;
            if(sum<0)
                return false;
            if(sum<arr[n-1])
                return existsSum(arr, n-1,sum);
            return existsSum(arr, n-1,sum) || existsSum(arr, n-1, sum-arr[n-1])  ;
        }

Это превышает ограничение по времени. Я не могу понять, как это влияет на время выполнения при изменении последовательности. Пожалуйста, помогите.

Ответы [ 2 ]

3 голосов
/ 19 марта 2020

Обратите внимание, что || имеет короткое замыкание, т. Е. В a || b, если a истинно, b не оценивается.

Разница между двумя операндами || является то, что existsSum(arr, n-1, sum-arr[n-1]) «добавляет» текущий элемент в список элементов, который суммируется с общей суммой, а existsSum(arr, n-1, sum) нет.

В первом фрагменте кода, если existsSum(arr, n-1, sum-arr[n-1]) истинно, existsSum(arr, n-1, sum) даже не вызывается. Представьте, что я вызываю это с массивом [1,2,3] и суммой 6. Первый операнд будет возвращать true при каждом рекурсивном вызове, и нет необходимости оценивать второй операнд.

Аналогично, во втором фрагменте кода сначала запускается existsSum(arr, n-1, sum), а если true, existsSum(arr, n-1, sum-arr[n-1]) не вызывается. Однако existsSum(arr, n-1, sum) редко может возвращать true самостоятельно . Под этим я подразумеваю, что для вызова existsSum(arr, n-1, sum), возвращающего значение true, значение true должно быть получено из рекурсивного вызова existsSum(arr, n-1, sum-arr[n-1]). Вы можете убедиться в этом, проанализировав различные ветви. (две ветви, которые возвращают true, это sum==0 и arr[n-1] == sum. Надеемся, вы согласитесь, что обе встречаются редко) Это означает, что возврат (то есть вызов existsSum(arr, n-1, sum-arr[n-1])) обязательно произойдет для existsSum(arr, n-1, sum).

В худшем случае эти два фрагмента кода совпадают.

0 голосов
/ 19 марта 2020

Это должно быть O (n) 

public static boolean sumExists(int [] in, int sum) {
    //You might be able to get away with just sorting the values and not copying it.
    int [] input = Arrays.copyOf(in, in.length);
    Arrays.sort(input);
    int currentSum = 0;
    int startIdx = 0;
    for (int i = 0; i < input.length; i++) {
        if (currentSum > sum) {
            while (currentSum > sum && startIdx < i) {
                currentSum -= input[startIdx++];
            }
        }

        if (currentSum == sum) {
            return true;
        } 
        currentSum += input[i];
    }
    return false;
}
...