Jitesh Gala Ответов: 3

Каким должен быть мыслительный процесс по поводу решения этого вопроса.

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]


Учитывая эти проблемы, мне нужна помощь по:
1) Каким должен быть мой подход к решению подобных вопросов.
2) в каком направлении я должен думать или на каком основании я должен начать думать для решения этих вопросов.

Заранее спасибо.

PS:мне не нужно решение, но я не могу придумать никакой отправной точки.

Что я уже пробовал:

я пробовал линейный способ мышления, но этого недостаточно.

Richard MacCutchan

Я бы предложил взять каждое число по очереди и использовать его и любые другие значения, чтобы увидеть, складываются ли они в цель. Учитывая, что вы можете использовать одни и те же числа более одного раза, это потенциально длительный процесс. Один дополнительный шаг, который вы можете попробовать, - это разделить цель на текущее число, чтобы увидеть, сколько раз она может поместиться. Тогда это дало бы еще одно целевое значение для поиска. Например, деление 8 на 2 дает немедленный ответ в приведенном выше примере.

3 Ответов

Рейтинг:
2

Patrice T

Цитата:
я пробовал линейный способ мышления, но этого недостаточно.

Что такое "линейный путь"?

Когда у вас нет известного эффективного алгоритма для решения проблемы, вы должны вернуться к поиску грубой силы.
Грубая сила пробует все возможные комбинации, чтобы получить все ответы.
Решение задачи вручную - это хороший способ получить первый алгоритм.
Атака грубой силы - Википедия[^]

Рейтинг:
1

OriginalGriff

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

Затем создайте несколько новых наборов чисел и попробуйте слепо следовать инструкциям. Сработало ли это? Если нет, вернитесь и улучшите инструкции. Пробовать снова.
Когда инструкции работают, у вас есть алгоритм и, вероятно, что-то достаточно близкое к псевдокоду.
Теперь вы можете начать думать о реализации этого, как о компьютерной программе - инструкции модифицируются для получения фактического псевдокода, и вы можете начать реализовывать и тестировать это.

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

Это не "решение" конкретной проблемы - но вы не просили об этом, и мы, вероятно, не дали бы вам его, если бы вы это сделали, - это основа общего метода мышления о проблемах и их решениях.

Рейтинг:
0

Pete O'Hanlon

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

Другими словами, прежде чем пытаться решить проблему, убедитесь, что вы знаете, в чем заключается вся проблема. Как только вы это сделаете, вашим следующим шагом будет перестать думать о том, как написать программу для этого. Сделайте шаг назад и подумайте, как бы вы сделали это сами. Не беспокойтесь о таких вещах, как алгоритмическая сложность или структуры программирования; просто запишите несколько примеров и используйте ручку и бумагу, чтобы попробовать эту задачу.

(Быстрый намек, если у вас есть 1 в ваших потенциальных значениях, то вы можете оптимизировать свою проблему, сказав, что ваше первое решение будет использовать 1, общее количество раз).

Patrice T

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

Pete O'Hanlon

Итак, какую из этих двух оптимизаций, по вашему мнению, ОП должен сбрасывать со счетов, когда они пишут свое решение грубой силы. Вот почему я сказал, что вы перестаете думать о том, как вы пишете программу, и почему вы думаете о том, как вы будете делать это сами. Вы бы проигнорировали первую оптимизацию, если бы делали это сами? Вы бы проигнорировали второе, которое я вставил, если бы вы делали это сами, или вы не согласились бы, что это вещи, которые вы сделали бы инстинктивно заранее?