# Why does greedy approach of constructing De Bruijin Sequence work?

I have recently discovered a greedy algorithm to construct De Bruijin Sequence. The greedy approach (prefer-largest specifically) works like the following:

1. Start with a sequence of all 0's of length n - 1 where n is the order of De Bruijin Sequence.
2. For k^n times (where 0...k-1 are the possible digits in the strings in the sequence), check from k - 1 to 0 (always try to append the largest digit) to see if the last n substring of the currently built sequence is a unique combination (this is kept track of using a set)

I have implemented this and it works but my question is WHY DOES IT WORK? I don't have master's in algorithms or math so if you can explain this in relatively plain terms, I would really appreciate it

• I think the easiest answer is that you're using a set to keep track of unique combinations. Because of this operation, you ensure that you will never create a duplicate in the sequence. In other words, when you "check...to see if the last n substring...is a unique combination", you have effectively ensured that you will never add a duplicate. The only other problem that may occur is that you don't add all $k^n$ sequences, which won't happen because you go through $k^n$ sequences, which are all that are required. Mar 8 at 4:12
• The key here is that you always to try to append the highest digit to the sequence. If you try to append from 0, you will end up with a wrong sequence. It's almost like magic. This is the part I am having a really hard time understanding or finding out why Mar 9 at 13:36