When to use ArrayList over array in recursion
So I have this problem. I was trying to code a program to print all the valid possible arrangements of brackets i.e. for 3 brackets we can have ((())), (()()), ()()(), (())() etc.
I have a working code
public static void main(String[] args) {
int number = 3; // No. of brackets
int cn = number;
int on = number;
// open and closed brackets respectively
char[] sol = new char[6];
printSol(on, cn, sol, 0);
}
public static void printSol(int cn, int on, char[] sol, int k) {
if (on == 0 && cn == 0) {
System.out.println("");
for (int i = 0; i < 6; i++) {
System.out.print(sol[i]);
}
}
else {
if (on > 0) {
if (cn > 0) {
sol[k] = '(';
printSol(on - 1, cn, sol, k + 1);
}
}
if (cn > on) {
sol[k] = ')';
printSol(on, cn - 1, sol, k + 1);
}
}
}
Now the problem is that I want to do this using ArrayList instead of using char array. I tried but am getting errors. If anyone has any suggestions please let me know. The main purpose of asking this question is that I want to know when shall I prefer ArrayLists over arrays in Recursion problems.
P.S. I am sorry for the poor indentation as I had to type the whole program due to surfing restrictions and also thre might be some syntax errors but I tried my be开发者_如何学Pythonst. Thanks Mohit
I think you're doing just fine using char[]
. It's quick and it's to the point.
I'd say most recursion problems you face in practice don't follow this pattern. That's because typically with problems demanding recursion you're performing a search on a search tree for one specific goal (one specific leaf node on a tree). You're performing iteration: you're trying to visit every leaf node on a tree, and perform an action for each.
With the common search algorithms (like a depth-first search), you thus wouldn't need to prepare the result as you recurse, but rather as you unwind, after you've found the goal.
But for cases where you do, char[]
works great. You're basically simulating a stack through the parameters sol
and k
(sol holds the data while k points to the top of the stack). As others have noticed, you could use a stack directly (by passing a Deque<Character>
implementation, commonly a LinkedList
).
In my mind ArrayList
is a step backwards. If you're going to use a collection, use one made for the problem.
Edit: Here's an untested implementation using a Deque instead:
public static void printSol(int cn, int on, Deque<Character> sol) {
if (on == 0 && cn == 0) {
System.out.println("");
for ( Iterator<Character> it = sol.descendingIterator(); it.hasNext(); ) {
System.out.println(it.next());
}
}
else {
if (on > 0) {
if (cn > 0) {
sol.push('(');
printSol(on - 1, cn, sol);
sol.pop();
}
}
if (cn > on) {
sol.push(')');
printSol(on, cn - 1, sol);
sol.pop();
}
}
}
//...
printSol(3, 3, new ArrayDeque<Character>(6));
As you can see, very few changes.
Edit 2: One thing we haven't discussed at all for this specific problem is StringBuilder
.
StringBuilder is a mutable String type that allows you to easily append and remove characters. This would be a great solution for this problem as well:
public static void printSol(int cn, int on, StringBuilder sol) {
if (on == 0 && cn == 0) {
System.out.println(sol);
}
else {
if (on > 0) {
if (cn > 0) {
sol.append('(');
printSol(on - 1, cn, sol);
sol.deleteCharAt(sol.length()-1);
}
}
if (cn > on) {
sol.append(')');
printSol(on, cn - 1, sol);
sol.deleteCharAt(sol.length()-1);
}
}
}
You want to avoid passing large data structures by-value while recursing as it can consume a lot of memory. That's about the only thing I can think of, in general. Passing a reference to an array or ArrayList is ok. I prefer ArrayList in general.
Look at Java's Stack
class for this problem in particular.
I realized nobody (including myself) actually answered your question. I think you've been convinced using an ArrayList
isn't desirable here. But how could you make it work?
The easiest way is to basically fake a stack with it:
public static void printSol(int cn, int on, ArrayList<Character> sol) {
//...
sol.add('(');
printSol(on - 1, cn, sol);
sol.remove(sol.size() - 1);
精彩评论