На вопрос:
Дано n различных положительных целых чисел, целое число k и число
цель. Найти k чисел, где сумма является целью. Верните сколько
решения есть?
Тестовый пример: A [] = {1,2,3,4}, k = 2, target = 5.
Есть 2 решения: [1,4] и [2,3].
Так что верните 2.
Мой код:
public class Solution {
private int res = 0;
public int kSum(int[] A, int k, int target) {
Arrays.sort(A);
DFS(A, k, target, 0 );
return res;
}
private void DFS(int[] A, int k, int target, int idx) {
if (target < 0) return;
if (k == 0) {
if (target == 0) res += 1;
return;
}
for (int i = idx; i < A.length; i++ ) {
DFS(A, k - 1, target - A[i], i + 1);
DFS(A, k, target, i + 1);
}
}
}
Для приведенного выше кода он дает мне вывод 6 (не 2) ;
Но , когда я изменяю последние 2 строки с:
DFS(A, k - 1, target - A[i], i + 1);
DFS(A, k, target, i + 1);
до:
private void DFS(int[] A, int k, int target, int idx, List<Integer> temp) {
..
temp.add(A[i]);
DFS(A, k - 1, target - A[i], i + 1, temp);
temp.remove(temp.size() - 1);
Тогда результат становится просто правильным, это 2, а не 6.
Я действительно не могу сказать никакой разницы между кодом выше и ниже.
Может ли кто-нибудь помочь мне и сказать мне, почему выше не так.
Большое спасибо.