LeetCode – Suma combinada (Java)

Dado un conjunto de números candidatos (C) y un número objetivo (T), encuentre todas las combinaciones únicas en C donde los números candidatos sumen T. El mismo número repetido puede elegirse entre C un número ilimitado de veces.

Nota: Todos los números (incluido el objetivo) serán números enteros positivos. Los elementos de una combinación (a1, a2, …, ak) deben estar en orden no descendente. (es decir, a1 <= a2 <= ... <= ak). El conjunto de soluciones no debe contener combinaciones duplicadas. Por ejemplo, dado el conjunto candidato 2, 3, 6, 7 y el objetivo 7, un conjunto de solución es:

[7] 
[2, 2, 3] 

Solución Java

La primera impresión de este problema debería ser la búsqueda en profundidad (DFS). Para resolver el problema de DFS, la recursividad es una implementación normal.

El siguiente ejemplo muestra cómo funciona DFS:

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    helper(candidates, 0, target, 0, temp, result);
    return result;
}
 
private void helper(int[] candidates, int start, int target, int sum,
                    List<Integer> list, List<List<Integer>> result){
    if(sum>target){
        return;
    }
 
    if(sum==target){
        result.add(new ArrayList<>(list));
        return;
    }
 
    for(int i=start; i<candidates.length; i++){
        list.add(candidates[i]);
        helper(candidates, i, target, sum+candidates[i], list, result);
        list.remove(list.size()-1);
    }
}