# Draw the recursion trace for the execution of the method PuzzleSolve(3, S, U)

Question:

Draw the recursion trace for the execution of the method PuzzleSolve(3, S, U) (Code Fragment 5.11), where S is empty and U = {a,b,c,d}. (Page 221 of the book mentioned below – R-5.6) Here is code Fragment 5.11 (page 213) from Goodrich, Michael T., Roberto Tamassia, Michael Goldwasser. Data Structures and Algorithms in Java, 6th Edition Algorithm PuzzleSolve(k, S, U): Input: An integer k, sequence S, and set U Output: An enumeration of all k-length extensions to S using elements in U without repetitions for each e in U do Add e to the end of S Remove e from U if k == 1 then Test whether S is a configuration that solves the puzzle if S solves the puzzle then add S to output else PuzzleSolve(k ? 1, S, U ) Remove e from the end of S Add e back to U

``````PuzzleSolver.java

import java.util.Iterator;

public class PuzzleSolver {
private static class QueueSet<T> extends LinkedHashSet<T> {
private static final long serialVersionUID = 7965261432562813003L;

public boolean offer(T element) {
}

public T poll() {
Iterator<T> it = iterator();
if (it.hasNext()) {
T first = it.next();
it.remove();
return first;
} else {
return null;
}
}
}

public static void main(String[] args) {
QueueSet<Character> qs = new QueueSet<>();
qs.offer('a');
qs.offer('b');
qs.offer('c');
qs.offer('e');

puzzleSolve(3, "", qs);
}

private static void puzzleSolve(int k, String s, QueueSet<Character> u) {
for (int i = 0; i < u.size(); i++) {
// Remove e from u
Character element = u.poll();

// Add e to the end of s
s = s + element;

if (k == 1) {
// Test whether s is a configuration that solves the puzzle
// if s solves the puzzle then add s to output
System.out.println(s);
} else {
puzzleSolve(k - 1, s, u);
}

// Remove e from the end of s
s = s.substring(0, s.length() - 1);

// Add e back to U
u.offer(element);
}
}

}``````