Это мой подход к проблеме. Я не использовал рекурсию или возврат с возвратом, как мы предполагали, но сделал это итеративно и получил ошибку превышения лимита времени. Я думаю, что мое решение правильное, несмотря на то, что оно очень запутанное и длинное. Может ли кто-нибудь помочь мне усовершенствовать его и немного исправить ошибки, которые я могу упустить из виду? Я не ищу совершенно другое решение, использующее рекурсию, а лишь настраиваю свое текущее, чтобы оно проходило все тестовые случаи.
https://leetcode.com/problems/combination-sum /description/
Для получения массива различных целых чисел-кандидатов и целевого целого числа, вернуть список всех уникальных комбинаций кандидатов, в которых сумма выбранных чисел равна целевому значению. Вы можете возвращать комбинации в любом порядке.
Одно и то же число можно выбирать из кандидатов неограниченное количество раз. Две комбинации уникальны, если
частота хотя бы одного из выбранных чисел различна.
Контрольные примеры генерируются таким образом, чтобы количество уникальных комбинаций, сумма которых соответствовала целевому значению, меньше 150 комбинаций для данного ввода.
Пример 1:
Ввод: кандидаты = [2,3,6,7], цель = 7
Вывод: [[2,2,3],[7]]
Объяснение:
2 и 3 являются кандидатами, а 2 + 2 + 3 = 7. Обратите внимание, что 2 может может использоваться несколько раз.
7 является кандидатом, а 7 = 7.
Это единственные две комбинации.
Пример 2:
Ввод: кандидаты = [2,3,5], цель = 8
Выход: [[2,2,2,2],[2,3,3],[3,5]]
Пример 3 :
Ввод: кандидаты = [2], цель = 1
Вывод: []
class Solution {
public List combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
int sum = 0;
ArrayList list = new ArrayList();
List finalL = new ArrayList();
for(int i = 0; i< candidates.length; i++) {
boolean circ = true;
int temp = 2*candidates;
sum = 0;
boolean b = true;
int j;
j = i;
while(b==true) {
if(sum>= target) {
if(sum==target) {
finalL.add(list);
}
if(j== candidates.length-1) {
circ = true;
int x;
x = list.get(list.size()-1);
for(int k = 0; k< candidates.length; k++) {
if(x == candidates[j]) {
j = k+1;
}
}
}
else{j = j+1;
circ = false;}
temp = list.get(list.size()-1) + list.get(list.size()-1);
list.remove(list.size() - 1);
list.remove(list.size() - 1);
sum = 0;
for (int num : list) {
sum += num;
}
while(sum< target) {
if(circ==true) {
sum = sum + candidates[j];
list.add(candidates[j]);
}
else if(candidates[j]< temp) {
if(j== candidates.length-1) {
b = false;
break;
}
j++;
}
else if(candidates[j]>=temp) {
sum = sum + candidates[j];
list.add(candidates[j]);}
}
}
}
}
return finalL;
}
}
Подробнее здесь: https://stackoverflow.com/questions/785 ... g-leetcode
