Dada una lista de números y un número objetivo, escriba un programa para determinar si el número objetivo se puede calcular aplicando operaciones «+ – * /» a la lista de números. Puede asumir que () se agrega automáticamente cuando es necesario. Se debe colocar un operador entre cada dos números consecutivos. Por tanto, se debe utilizar cada número.
Por ejemplo, dado {1,2,3,4} y 21, devuelve verdadero. Porque (1 + 2) * (3 + 4) = 21
Solución Java
Este es un problema de partición que se puede resolver utilizando la búsqueda en profundidad.
public boolean isReachable(ArrayList<Integer> list, int target) { if (list == null || list.size() == 0) return false; int i = 0; int j = list.size() - 1; ArrayList<Integer> results = getResults(list, i, j); for (int num : results) { if (num == target) { return true; } } return false; } public ArrayList<Integer> getResults(ArrayList<Integer> list, int left, int right) { ArrayList<Integer> result = new ArrayList<Integer>(); if (left > right) { return result; } else if (left == right) { result.add(list.get(left)); return result; } for (int i = left; i < right; i++) { ArrayList<Integer> result1 = getResults(list, left, i); ArrayList<Integer> result2 = getResults(list, i + 1, right); for (int x : result1) { for (int y : result2) { result.add(x + y); result.add(x - y); result.add(x * y); if (y != 0) result.add(x / y); } } } return result; } |
