Complete the private combinations method. Modify the code so that it is possible to compute combinations(“ABCD”,2) with fewer than 20 calls and combinations(“ABCDE”,3) with fewer than 30 calls. import static org.junit.Assert.*; import java.util.ArrayList; import org.junit.Test; /** * Recursive computation of all combinations of k characters from a string s. * */ public class Combinations { private static int recusiveCalls = 0; /** * Generate all combinations of the characters in the string s with length * k. * * @param s * a string. * @param k * the length of the combinations * @return a list of all of the combinations of the strings in s. */ public static ArrayList combinations(String s, int k) { return combinations("", s, k); } /** * Recursive Problem Transformation: * * Generate all combinations of length k of the characters in rest prefixed * with the characters in prefix. This is very similar to the subset method! * Note k is the total length of each string in the returned ArrayList. * * * For example: * combinations("", "ABC", 2) -> "" before {AB, AC, BC} * -> {AB, AC, BC} * * combinations("A", "BC", 2) -> A before {BC, B, C, ""} * -> {AB, AC} * * combinations("", "BC", 2) -> "" before {BC, B, C, ""} * -> {BC} * */ private static ArrayList combinations(String prefix, String rest, int k) { recusiveCalls++; } }
Complete the private combinations method. Modify the code so that it is possible to compute combinations(“ABCD”,2) with fewer than 20 calls and combinations(“ABCDE”,3) with fewer than 30 calls.
import static org.junit.Assert.*;
import java.util.ArrayList;
import org.junit.Test;
/**
* Recursive computation of all combinations of k characters from a string s.
*
*/
public class Combinations {
private static int recusiveCalls = 0;
/**
* Generate all combinations of the characters in the string s with length
* k.
*
* @param s
* a string.
* @param k
* the length of the combinations
* @return a list of all of the combinations of the strings in s.
*/
public static ArrayList<String> combinations(String s, int k) {
return combinations("", s, k);
}
/**
* Recursive Problem Transformation:
*
* Generate all combinations of length k of the characters in rest prefixed
* with the characters in prefix. This is very similar to the subset method!
* Note k is the total length of each string in the returned ArrayList.
*
* <code>
* For example:
* combinations("", "ABC", 2) -> "" before {AB, AC, BC}
* -> {AB, AC, BC}
*
* combinations("A", "BC", 2) -> A before {BC, B, C, ""}
* -> {AB, AC}
*
* combinations("", "BC", 2) -> "" before {BC, B, C, ""}
* -> {BC}
* </code>
*/
private static ArrayList<String> combinations(String prefix, String rest,
int k) {
recusiveCalls++;
}
}
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 2 images
