Particionar la string dada de tal manera que la i-ésima substring sea la suma de (i-1)’ésima y (i-2)’nd substring. Ejemplos:
Input : "11235813" Output : ["1", "1", "2", "3", "5", "8", "13"] Input : "1111223" Output : ["1", "11", "12", "23"] Input : "1111213" Output : ["11", "1", "12", "13"] Input : "11121114" Output : []
1. Iterar a través de la string dada eligiendo 3 números (primero, segundo y tercero) a la vez a partir de un dígito cada uno. 2. Si primero + segundo = tercero, llame recursivamente a check() con segundo como primero y tercero como segundo. El tercero se elige en función del siguiente número posible de dígitos. (El resultado de la suma de dos números puede tener un máximo de dígitos del segundo y tercero + 1) 3. De lo contrario, primero incremente el tercero (agregando más dígitos) hasta el límite (Aquí el límite es la suma del primero y el segundo). 4. Después de incrementar el tercio, surgen los siguientes casos. a) Cuando no coincida, incremente el segundo desplazamiento. b) Cuando no coincida, incremente el primer desplazamiento. c) Nota: Una vez que se realiza una llamada a check() después de incrementar el tercer desplazamiento, no modifique el segundo ni el primero, ya que ya están finalizados. 5. Cuando se llega al final de la string y se cumple la condición, agregue «segundo» y «tercero» a la lista vacía. Mientras revierte la pila recursiva, anteponga el «primero» a la lista para que se conserve el orden.
Java
// Java program to check if we can partition a
// string in a way that value of i-th string is
// sum of (i-1)-th and (i-2)-th substrings.
import java.util.LinkedList;
public class SumArray {
private static LinkedList<Integer> resultList =
new LinkedList<>();
private static boolean check(char[] chars, int offset1,
int offset2, int offset3, boolean freezeFirstAndSecond) {
// Find subarrays according to given offsets
int first = intOf(subArr(chars, 0, offset1));
int second = intOf(subArr(chars, offset1, offset2));
int third = intOf(subArr(chars, offset1 + offset2, offset3));
// If condition is satisfied for current subarrays
if (first + second == third) {
// If whole array is covered.
if (offset1 + offset2 + offset3 >= chars.length) {
resultList.add(first);
resultList.add(second);
resultList.add(third);
return true;
}
// Check if remaining array also satisfies the condition
boolean result = check(subArr(chars, offset1,
chars.length - offset1), offset2, offset3,
Math.max(offset2, offset3), true);
if (result) {
resultList.addFirst(first);
}
return result;
}
// If not satisfied, try incrementing third
if (isValidOffSet(offset1, offset2, 1 + offset3, chars.length)) {
if (check(chars, offset1, offset2, 1 + offset3, false))
return true;
}
// If first and second have been finalized, do not
// alter already computed results
if (freezeFirstAndSecond)
return false;
// If first and second are not finalized
if (isValidOffSet(offset1, 1 + offset2, Math.max(offset1,
1 + offset2), chars.length)) {
// Try incrementing second
if (check(chars, offset1, 1 + offset2,
Math.max(offset1, 1 + offset2), false))
return true;
}
// Try incrementing first
if (isValidOffSet(1 + offset1, offset2, Math.max(1 + offset1,
offset2), chars.length)) {
if (check(chars, 1 + offset1, offset2, Math.max(1 + offset1,
offset2), false))
return true;
}
return false;
}
// Check if given three offsets are valid (Within array length
// and third offset can represent sum of first two)
private static boolean isValidOffSet(int offset1, int offset2,
int offset3, int length) {
return (offset1 + offset2 + offset3 <= length &&
(offset3 == Math.max(offset1, offset2) ||
offset3 == 1 + Math.max(offset1, offset2)));
}
// To get a subarray with starting from given
// index and offset
private static char[] subArr(char[] chars, int index, int offset) {
int trueOffset = Math.min(chars.length - index, offset);
char[] destArr = new char[trueOffset];
System.arraycopy(chars, index, destArr, 0, trueOffset);
return destArr;
}
private static int intOf(char... chars) {
return Integer.valueOf(new String(chars));
}
public static void main(String[] args) {
String numStr = "11235813";
char[] chars = numStr.toCharArray();
System.out.println(check(chars, 1, 1, 1, false));
System.out.println(resultList);
}
}
true [1, 1, 2, 3, 5, 8, 13]
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)