Рекурсивно определить, содержит ли набор чисел два подмножества, равные по сумме - PullRequest
Новая
       21

Рекурсивно определить, содержит ли набор чисел два подмножества, равные по сумме

0 голосов
/ 31 октября 2018

Мне нужно выяснить, как рекурсивно определить, существует ли выбор элементов, такой, чтобы сумма выбранных элементов была такой же, как сумма невыбранных элементов, заданных списком целых чисел.

Так, например, набор nums = [1,3,5,3] возвращает true , поскольку подмножествами могут быть [3,3] и [1,5], то есть оба списка добавляют до 6, поэтому метод должен возвращать true . Если эти подмножества отсутствуют, они должны вернуть false .

У меня есть код: 

private static boolean canFind(int[] nums, int index, int sumOne, int sumTwo) {
    if (index == nums.length) {
        return false;
    }

    if (oneSum == twoSum) {
        return true;
    }

    if (oneSum < twoSum) {
        return canFind(nums, index + 1, sumOne + nums[index], sumTwo);
    }

    return canFind(nums, index + 1, sumOne, sumTwo + nums[index]);
}

но я не могу понять, почему это не работает или даже почему это так.

1 Ответ

0 голосов
/ 31 октября 2018

Идея рекурсивного метода canFind():

  • Если я обработал числа до позиции index и пока собрали две суммы sumOne и sumTwo, возможно ли найти решение с оставшимися номерами?

Прежде чем подробно рассмотреть ваш код, давайте уточним задачу (если я правильно понимаю): для правильного решения необходимо подсчитать каждое число либо в sumOne, либо в sumTwo. Пропуск числа или подсчет числа в обеих суммах не допускаются.

Итак, в любой момент процесса решения у вас есть выбор: добавить текущий номер в sumOne или в sumTwo, и это то, что вы правильно делаете в двух рекурсивных вызовах 

    canFind(nums, index + 1, sumOne + nums[index], sumTwo)

и 

    canFind(nums, index + 1, sumOne, sumTwo + nums[index])

Но есть проблема с вызовами. Вы не можете знать, будет ли правильное добавление текущего номера к sumOne или sumTwo для решения, поэтому вы должны попробовать оба способа и вернуть true, если один из них завершится успешно. Ваш код добавляет к sumOne, если он меньше, в противном случае к sumTwo. Хотя это кажется правдоподобным, это не обязательно приводит к решению. Таким образом, вы должны изменить эту часть на 

    if (canFind(nums, index + 1, sumOne + nums[index], sumTwo)) {
        // if there's some solution by adding to sumOne, we're finished.
        return true;
    } else if (canFind(nums, index + 1, sumOne, sumTwo + nums[index])) {
        // if there's some solution by adding to sumTwo, we're finished.
        return true;
    } else {
        // if both tries didn't succeed, thre's no solution 
        // starting from the given situation
        return false;
    }

Как долго мы должны продолжать пробовать числа? Пока мы не доберемся до конца массива, так как нам не разрешено пропускать любое число.

И когда мы достигаем конца массива, у нас есть решение или нет? Это решение, если обе суммы равны.

Итак, прежде чем пытаться выполнить рекурсивные вызовы, мы должны проверить конец массива: 

    if (index == nums.length) {
        if (sumOne == sumTwo) {
            return true;
        } else {
            return false;
        }
    }

Собираем все вместе: 

private static boolean canFind(int[] nums, int index, int sumOne, int sumTwo) {
    if (index == nums.length) {
        // if we're at the end of the array, we can compare the sums
        // to decide whether this is a solution.
        if (sumOne == sumTwo) {
            return true;
        } else {
            return false;
        }
    }
    if (canFind(nums, index + 1, sumOne + nums[index], sumTwo)) {
        // if there's some solution by adding to sumOne, we're finished.
        return true;
    } else if (canFind(nums, index + 1, sumOne, sumTwo + nums[index])) {
        // if there's some solution by adding to sumTwo, we're finished.
        return true;
    } else {
        // if both tries didn't succeed, thre's no solution 
        // starting from the given situation
        return false;
    }
}

Это должно в основном делать работу.

...