Алгоритм C # - перечисление всех перестановок числа

Question

Это своего рода продолжение вопроса, который я опубликовал ранее (алгоритм C # - найдите наименьшее количество необходимых объектов ), но немного другой.

Учитывая, что у меня есть следующий код:

var max = 80;
var list = new[]{10,20,30,40,50, 60);

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

Массив будет содержать {40, 40}, {50, 30}, {40,30, 10} и т. Д. *

Answer 1

Вы захотите перебрать все числа в порядке убывания. Затем рекурсивно добавьте каждый следующий нисходящий номер в последовательности. Каждый раз, когда сумма совпадает, обратите внимание, что комбо, всплывающее и двигаться дальше. Когда ваша предварительная сумма переместит вас через переменную max, выскочите из функции к следующей функции в стеке. Если максимальное значение еще не достигнуто, последовательно добавьте следующий номер вниз в последовательности. Таким образом, вы покроете все возможные последовательности без дубликатов (если только в данном наборе нет дубликатов, и в этом случае вы захотите этот дубликат). На самом деле это будет не слишком много кода.

Answer 2

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

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

РЕДАКТИРОВАТЬ: На самом деле, если вы разрешаете повторные номера, это не работает. Альтернативный алгоритм (который допускает повторы, но не любые отрицательные значения) состоит в том, чтобы в основном продолжать добавлять наибольшее число в списке, а затем возвращаться назад, если вы перешли цель.