Учитывая массив целых чисел и число n, вычислите количество способов суммирования по n, используя целые числа

algorithm recursion

528 просмотра

1 ответ

435 Репутация автора

Я видел эту проблему при подготовке к собеседованию.

Учитывая массив целых чисел и число n, вычислите количество способов суммирования по n, используя целые числа

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

public static int count(List<Integer> list, int n) {
    System.out.print(list.size() + ", " + n);
    System.out.println();
    if (n < 0 || list.size() == 0)
      return 0;
    if (list.get(0) == n)
      return 1;
    int e = list.remove(0);
    return count(list, n) + count(list, n - e);
  }

Я попытался использовать [10, 1, 2, 7, 6, 1, 5] для целых и установить n равным 8. Результат должен быть 4. Однако я получил 0. Я попытался напечатать то, что у меня есть на каждом слое стека для отладки, как показано в коде. Вот что я имею:

7, 8
6, 8
5, 8
4, 8
3, 8
2, 8
1, 8
0, 8
0, 3
0, 7
0, 2
0, 1
0, 6
0, 7
0, -2

Этот результат смущает меня. Я думаю, что это выглядит правильно от начала до (0, 3). Начиная с (0, 7), это выглядит неправильно для меня. Я ожидаю (1, 7) там. Потому что, если я правильно понимаю, это для вызова count (list, n - e) со второго по нижний уровень в стеке. Операция со списком на нижнем уровне не должна влиять на список на текущем слое. Итак, мои вопросы:

  1. почему (0, 7) вместо (1, 7) основано на моем текущем коде?
  2. Какие настройки я должен сделать с моим текущим кодом, чтобы получить правильный результат?

Спасибо!

Автор: Fei Qu Источник Размещён: 18.07.2016 08:49

Ответы (1)


5 плюса

5944 Репутация автора

Решение

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

Поскольку список передается по ссылке , в конечном итоге происходит то, что вы вызываете рекурсивно, removeпока в списке больше ничего не останется, а затем все ваши рекурсивные вызовы будут возвращаться0

Что вы можете сделать, это создать две копии списка на каждом рекурсивном шаге. Однако это было бы слишком неэффективно.

Лучшим способом было бы использовать индекс, iкоторый отмечает элемент в списке, который просматривается во время вызова:

public static int count(List<Integer> list, int n, int i) {
    //System.out.print(list.size() + ", " + n);
    //System.out.println();
    if (n < 0 || i <= 0)
      return 0;

    int e = list.get(i);  // e is the i-th element in the list
    if (e == n)
      return 1 + count(list, n, i-1);   // Return 1 + check for more possibilities without picking e

    return count(list, n, i-1) + count(list, n - e, i-1);   // Result if e is not picked + result if e is picked
}

Затем вы должны пройти yourList.size() - 1для iна вызов исходной функции.

Еще один момент заключается в том, что когда вы return 1, вы все равно должны добавить количество возможностей, когда ваш элемент eне выбран, чтобы быть частью суммы. В противном случае, если - например - ваш последний элемент в списке был n, рекурсия закончилась бы только на первом шаге, возвращая 1и не проверяя на наличие более возможных комбинаций чисел.

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

Автор: Keiwan Размещён: 18.07.2016 09:20
Вопросы из категории :
32x32