DFS одно условие в этом действительно смущает меня - PullRequest
Новая
       7

DFS одно условие в этом действительно смущает меня

0 голосов
/ 04 июля 2018

На вопрос:

Дано 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. Я действительно не могу сказать никакой разницы между кодом выше и ниже. Может ли кто-нибудь помочь мне и сказать мне, почему выше не так. Большое спасибо.

1 Ответ

0 голосов
/ 04 июля 2018

Нет необходимости добавлять "DFS(A, k, target, i + 1);" Просто удали эту строку.

...