Thanks for the awesome structuring of combinatorial and backtracking approach. It helped me to understand the things very clearly.
Great!..
def backtrack(candidate):
if find_solution(candidate):
output(candidate)
return
# iterate all possible candidates.
for next_candidate in list_of_candidates:
if is_valid(next_candidate):
# try this partial candidate solution
place(next_candidate)
# given the candidate, explore further.
backtrack(next_candidate)
# backtrack
remove(next_candidate)
Awesome job on this one!
The link to “prune” the tree: https://algo.monster/articles/backtracking_pruning is not 404 not found
oh thanks for noticing, we’ve fixed it
Great article! Thank you! 
Here’s a simplified Java version. I came up with.
...
import java.util.ArrayList;
class Solution {
private static final String[] LETTERS = {"a", "b"};
public static List<String> letterCombination(int size) {
List<String> paths = new ArrayList<>();
buildLetterCombos(size, paths, 0, "");
return paths;
}
private static void buildLetterCombos(int size, List<String> paths, int index, String path) {
if (index == size) {
paths.add(path);
return;
}
for (String letter : LETTERS)
buildLetterCombos(size, paths, index + 1, path + letter);
}
...
}
Awesome explanations for a complex topic, only a few things I missed from reading this the first time that I submitted questions about.
One suggestion is to add the expectation for when n=0 and the constraints for n. It confused me that when n=0 the test expected an array with an empty string "", especially when printing the case after failure (it shows nothing in the output.) I expected the answer to be an empty array or that n > 0, since {""} doesn’t seem like a valid response.
If this is so simple why wasn’t this used?? My guess is that it moves away from the generalized template that they provided as a guide, the template that followed from the ternary tree printing exercise.
The paths.add in each stack frame required a paths.remove during the return to reset the state back to what it should be in that current node. Another way to say it is that paths.add was made for the next child node and then a call was made to this node with this new state that was appropriate for the child. After the return from this call to the child to the calling node, the paths.remove needed to be called to clean up this state of this stack frame. In this simplified java example there is no state change to the calling method, the update is done in the parameter so no clean up is necessary. However it hides what is really going on and thus although less verbose, is more confusing imo.
Great article - thank you!
Here’s what i came up with
...
import java.util.ArrayList;
class Solution {
static final char[] ALPHA = "ab".toCharArray();
public static List<String> letterCombination(int n) {
List<String> LIST = new ArrayList<>();
DFS(n, "", LIST);
return LIST;
}
public static void DFS(int n, String curr, List<String> list) {
if (curr.length() == n) { list.add(curr); return; }
for (int i = 0; i < ALPHA.length; i += 1) {
DFS(n, curr + ALPHA[i], list);
}
}
...
}
It’s possible to solve it using the length of path instead of the start_index:
def letter_combination(n: int) -> List[str]:
res = []
def dfs(path=[]):
if len(path) == n:
res.append("".join(path))
return
for letter in "ab":
path.append(letter)
dfs(path)
path.pop()
dfs()
return res
def letter_combination(n: int) -> List[str]:
def traverse(cur_path, combs, n):
if len(cur_path) == n:
combs.append(''.join(cur_path))
return
for child in ["a", "b"]:
cur_path.append(child)
traverse(cur_path, combs, n)
cur_path.pop()
combs = []
traverse([], combs, n)
return combs
I think the term Decision Tree is much more relevant than the State Space tree ,