# 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_code`s 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

+1

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â€ť.