Quiet Switch Patterns
Easy · backtracking
A small control panel has a row of n switches. Each switch is either on or off. If two switches that sit next to each other are both on, the panel buzzes loudly, so the engineers only allow settings where no two neighbouring switches are both on.
Write each setting as a string of n characters from left to right, using "1" for a switch that is on and "0" for a switch that is off. For example, with n = 3 the setting "101" is allowed, but "110" is not.
Return every allowed setting, each exactly once, sorted in ascending alphabetical order (so "0" comes before "1" at every position).
Examples
Example 1
Input: n = 2
Output: ["00", "01", "10"]
The setting "11" is left out because its two switches are neighbours that are both on.
Example 2
Input: n = 3
Output: ["000", "001", "010", "100", "101"]
Example 3
Input: n = 1
Output: ["0", "1"]
A single switch has no neighbours, so both settings are allowed.
Constraints
- 1 <= n <= 12