Проблема рекурсии Java

Question

У меня была проблема с вопросом об интервью на Java, нужна ваша помощь по этому вопросу.

Запишите **Java function** так, чтобы :: Учитывая массив целых, можно ли разделить целые числа на две группы, чтобы сумма этих двух групп была одинаковой с этими ограничениями: все значения, которые кратное 5 должно быть в одной группе, а все значения, кратные 3 (а не кратные 5), должны быть в другой. (Никаких петель не требуется.)

split53({1,1}) → true<br> split53({1, 1, 1}) → false<br> split53({2, 4, 2}) → true

PS: Это был вопрос для интервью для hewlett packard

Answer 1

Вопрос легко сводится к следующему: при наличии набора целых чисел numbers и целого числа target возможно ли найти подмножество numbers с суммой, равной target?
ПустьЯ знаю, если переход нуждается в разъяснении.

Это может быть решено с DP в O(numbers.size * target) времени.Идея заключается в следующем

1. Когда numbers.size равно 0, единственная достижимая сумма равна 0.
2. Предположим, у нас есть numbers == {1, 3}, в данном случае суммы {0, 1, 3, 4} доступны.Что если мы добавим еще один элемент к numbers, 4?Теперь все старые суммы все еще могут быть достигнуты и некоторые новые тоже: {0 + 4, 1 + 4, 3 + 4, 4 + 4}.Таким образом, для numbers == {1, 3, 4} доступны суммы {0, 1, 3, 4, 5, 7, 8}.
3. Таким образом, добавляя число к номеру, вы можете построить список доступных сумм.

Рабочий пример(он не обрабатывает отрицательные числа, но вы можете легко это исправить)

boolean splittable(int[] numbers, int target) {
    boolean[] reached = new boolean[target + 1];
    reached[0] = true;

    for (int number : numbers) {
        for (int sum = target - 1; sum >= 0; --sum) {
            if (reached[sum] && sum + number <= target) {
                reached[sum + number] = true;
            }
        }
    }

    return reached[target];
}

Запустите его

System.out.println(splittable(new int[]{3, 1, 4}, 7)); // => true
System.out.println(splittable(new int[]{3, 1, 4}, 6)); // => false

edit
Я только что заметил«рекурсивная» часть требования.Что ж, DP можно переписать как рекурсию с памяткой , если это сложное требование.Это сохранит сложность среды выполнения.

edit 2
В группах.Вы должны назначить элементы, кратные 3 или 5, соответствующим группам до того, как продолжите работу с алгоритмом.Скажем, сумма всех элементов равна s, сумма элементов, кратных 3, равна s3, а сумма элементов, кратных 5, но не 3, равна s5.В этом случае, после того, как вы присвоили эти «особые» элементы, вам нужно разделить остаток, чтобы сумма в одной группе была s/2 - s3, а в другой s/2 - s5.

Answer 2

Код, который, вероятно, меня уволят. Но работать будет: D

Полностью рекурсивный, одинаково смертельный.

public boolean split53(int[] nums) {
    return split_fn(0, nums, 0, 0, false, false);
}
public boolean split_fn(int start, int[] nums, int left, int right, boolean fiveLeft, boolean chosen) {
    if (start >= nums.length) {
        if (left == right) return true;
        return false;
    }
    if (nums[start] % 5 == 0) {
        if (!chosen) {
            return split_fn(start + 1, nums, left + nums[start], right, true, true) || split_fn(start + 1, nums, left, right + nums[start], false, true);
        } else {
            return split_fn(start + 1, nums, left + ((fiveLeft) ? nums[start] : 0), right + ((!fiveLeft) ? nums[start] : 0), fiveLeft, chosen);
        }

    }

    if (nums[start] % 3 == 0 && nums[start] % 5 != 0) {
        if (!chosen) {
            return split_fn(start + 1, nums, left + nums[start], right, false, true) || split_fn(start + 1, nums, left, right + nums[start], true, true);
        } else {
            return split_fn(start + 1, nums, left + ((!fiveLeft) ? nums[start] : 0), right + ((fiveLeft) ? nums[start] : 0), fiveLeft, chosen);
        }
    }
    //standard case
    return split_fn(start + 1, nums, left + nums[start], right, fiveLeft, chosen) || split_fn(start + 1, nums, left, right + nums[start], fiveLeft, chosen);

}

Answer 3

Вот реальное рекурсивное решение.

private boolean split2(int index, int[] nums, int sum1, int sum2) {
  if (index >= nums.length) {
    return sum1 == sum2;
  }

  if (split2(index + 1, nums, sum1 + nums[index], sum2)) {
    return true;
  }
  if (split2(index + 1, nums, sum1, sum2 + nums[index])) {
    return true;
  }

  return false; 
}

Этот код проходит помещение каждого элемента в одну из группы.Если в любой комбинации две группы равны, возвращается true.Никакие циклы не используются и только в одной функции.

Лучше всего для всех

edit: Ваша функция принимает в качестве входных данных 4 аргумента, тогда как вопрос получает в качестве входных данных только массивВы должны указать, что желаемую функцию можно выполнить с помощью вызова split2(0,nums,0,0);

Answer 4

Очень медленное, но рабочее решение:

static boolean canSplit(int[] arr, int lvl, int sum1, int sum2) {
        if (arr.length == lvl) {
            if (sum1 == sum2) {
                return true;
            } else {
                return false;
            }
        }
        if (arr[lvl] % 5 == 0) {
            return canSplit(arr, lvl + 1, sum1 + arr[lvl], sum2);
        } else if (arr[lvl] % 3 == 0) {
            return canSplit(arr, lvl + 1, sum1, sum2 + arr[lvl]);
        }
        return canSplit(arr, lvl + 1, sum1 + arr[lvl], sum2) ||
               canSplit(arr, lvl + 1, sum1, sum2 + arr[lvl]);
    }

Вызов функции:

canSplit(arr, 0, 0, 0);

Answer 5

Я не знаю, насколько быстрым или медленным является следующее решение. Но именно это рекурсивное решение для возврата, которое не использует циклов, как указано в вопросе.

Вот фрагмент кода:

public boolean split53(int[] nums) {
    int start = 0, firstPart = 0, secondPart = 0;
    if (split(start, nums, firstPart, secondPart)) {
        return true;
    }
    return false;
}

public boolean split(int start, int[] nums, int firstPart, int secondPart) {
    if (start >= nums.length) {
        return (firstPart == secondPart);
    }
    if ((start + 1) < nums.length
            && (nums[start] % 3 != 0)
            && (nums[start + 1] % 5 != 0)
            && split(start + 2, nums, firstPart + nums[start], secondPart
                    + nums[start + 1])) {
        return true;
    }
    if ((start + 1) < nums.length
            && (nums[start + 1] % 3 != 0)
            && (nums[start] % 5 != 0)
            && split(start + 2, nums, firstPart + nums[start + 1],
                    secondPart + nums[start])) {
        return true;
    }
    if ((nums[start] % 3 != 0)
            && split(start + 1, nums, firstPart + nums[start], secondPart)) {
        return true;
    }
    if ((nums[start] % 5 != 0)
            && split(start + 1, nums, firstPart, secondPart + nums[start])) {
        return true;
    }
    return false;
}

Надеюсь, это поможет.