Сложность алгоритма суммы подмножеств с некоторыми дополнительными условиями

Question

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

• Все кратные 5 должны быть включены.
• Если после 1 стоит число, кратное 5, то оно не должно быть включено.

Существует

Стандартное решение

  /*
   * Given an array of ints, is it possible to choose a group of some of the ints,
   * such that the group sums to the given target with these additional constraints:
   * all multiples of 5 in the array must be included in the group.
   * If the value immediately following a multiple of 5 is 1,
   * it must not be chosen. (No loops needed.)
   *
   * groupSum5(0, {2, 5, 10, 4}, 19) → true
   * groupSum5(0, {2, 5, 10, 4}, 17) → true
   * groupSum5(0, {2, 5, 10, 4}, 12) → false
   * groupSum5(0, {3, 5, 1}, 9) → false
   * groupSum5(0, {2, 5, 4, 10}, 12) → false
   * groupSum5(0, {3, 5, 1}, 5) → true
   * groupSum5(0, {1, 3, 5}, 5) → true
   * groupSum5(0, {1}, 1) → true
   */
  public boolean groupSum5(int start, int[] nums, int target) {
    if (start >= nums.length) return (target == 0);
    if (nums[start] % 5 == 0) {
       if (start < nums.length - 1 && nums[start + 1] == 1){
         return groupSum5(start + 2, nums, target - nums[start]);
       }
      return groupSum5(start + 1, nums, target- nums[start]);
    }
    return groupSum5(start + 1, nums, target - nums[start])
              || groupSum5(start + 1, nums, target);
  }

Мой подход

public boolean groupSum5(int start, int[] nums, int target) {
        final int len = nums.length;

        if (start == len) {
            return target == 0;
        }

        if (start > 0 && nums[start] == 1 && (nums[start- 1] % 5) == 0 ) {
            return groupSum5(start + 1, nums, target);
        }

        if (groupSum5(start + 1, nums, target - nums[start])) {
            return true;
        } if ((nums[start] % 5) != 0
                & groupSum5(start + 1, nums, target)) {
            return true;
        }
        return false;
    }

Какой из двух вышеуказанных тарифов лучше с точки зрения сложности времени?

Если я не ошибаюсь, стандартное решение или сложность первого решения выше экспоненциального (3 ^ n) ? Я предполагаю, что если принять во внимание рекурсивные вызовы, было бы правильно сказать, что сложность составляет (4 ^ n) ?

Answer 1

Ваш код неверен, я думаю. groupSum5 (0, [0, 1, 1], 1) возвращает false с вашим кодом, поскольку обе единицы исключены. И правильный groupSum5, и ваш - O (2 ^ n) в худшем случае. Хотя groupSum5 появляется в тексте 4 раза в первом фрагменте кода, только 2 из этих вызовов могут произойти в одном кадре стека