Backtracking Speedrun - Backtracking / Speedrun

Where in the code are we ensuring that the leaf node is a 1 bit difference from the start? Does the get_edges logic guarantee this to be the case? how so?

Basically there is a pattern we create by obtaining new_codes starting from the rightmost bit. For every k < n, when we flip the k-th bit from 0 to 1, we have visited all the numbers < 2^k, then the next 2^k elements are in reverse ordering as the previous 2^k elements (which ends in 2^k = 1<<k and is only the k-th bit is different than 0).

Could you please provide Java code solution for this problem ?

For Question 7 (return all possible permutations for a given nums array), on solution line 13, could you please explain the part that says .. && not used[i-1] ?

I run the code with and without the not operator and it works both ways. When I remove the user[i-1], it stops working though.

With not: you can interpret line 13 as “if the current number is a duplicate of the previous number, you should not use the current number if the previous number is not used”. Because we do not want to put a duplicate in the same index of path.

Without not: you interpret the condition as “if current and previous are duplicates, you cannot use current if previous is used” = you use k=current if no previous duplicate(s) are used, so during the next function call, we could start using the duplicate that was one index before k. So essentially, you reverse the deduplication process so that now we select duplicate elements starting from the largest index to smallest index.

Both ways are correct ways to duplicate the outputs, the not used[I-1] is more efficient though.

TLDR: at the same position of path the not used[i-1] avoids using the value at a larger index if the same value at a smaller index was not used, and without not, the deduplication goes in reverse (ie avoid using smaller index if larger index is not used). But we must use one of these to deduplicate.

For the 10th question, is this not the state space tree for n=2? The question asks for the state space tree for n=3. Is the image shown incorrect? A state space tree for n=3 would include integers with 3-bit representations, no?

1 Like


For Problem#10: could you please add the missing ^ sign in the problem description: 2^n and [0, 2^n - 1]

yes, #10’s answer can’t be correct for a range of 0:5. shouldn’t the resulting codes be 2n digits long?

I like this speedrun system. Thank you very much.
It will be greater if the time complexity of a problem is included in the speedrun.

yes , must be n=2. for 3 it must include 0-5 numbers in list

In the sentence " Select the correct implementation for is_valid that returns true to ranch, and false to prune." “ranch” should be “branch”.