Quiet Camera Layouts
All nonadjacent k-index subsets of 0 to n-1 in lexicographic order
A wildlife survey team has n camera stations arranged along a straight trail, numbered from 0 to n - 1. To avoid overlapping motion sensors, the team cannot activate two neighboring stations.
Return every possible layout that activates exactly k stations.
Each layout must be a list of station indices in strictly increasing order. Two selected indices must differ by at least 2. Return the layouts in lexicographic order: compare their first differing indices, with the smaller index coming first.
If no layout is possible, return an empty list. If k is 0, return a list containing the single empty layout: [[]].
Examples
Example 1
Input: n = 5, k = 2 Output: [[0,2],[0,3],[0,4],[1,3],[1,4],[2,4]]
With five stations and two cameras, enumerate all increasing pairs, excluding pairs of neighboring stations. Layouts beginning with station 0 come before layouts beginning with station 1.
Example 2
Input: n = 4, k = 3 Output: []
With four stations, three cameras cannot be placed without activating neighboring stations, so no layout is possible.
Example 3
Input: n = 3, k = 0 Output: [[]]
Activating zero cameras has exactly one layout: selecting no stations.
Constraints
- 0 <= n <= 24
- 0 <= k <= n
- Stations form a straight trail, not a circle; stations 0 and n - 1 are not neighbors unless n = 2.
The output can be exponential in n. A capacity-pruned backtracking solution takes O(1 + k * L) time, where L is the number of returned layouts, and O(k) auxiliary space excluding the output.
Hints
Show hint 1Hint 1
Build a layout one index at a time. After selecting station i, the next selected station must be at least i + 2.
Show hint 2Hint 2
If r stations still need to be selected, choosing the next index too far to the right leaves insufficient space. What is the largest next index that leaves room for r mutually nonadjacent stations?
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you count the layouts without constructing them?
- How would you change the enumeration if every two selected stations had to differ by at least a given distance d?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem