1155. Selections With No Two Consecutive Values
Given n distinct integers, print every selection in which no two chosen
values differ by exactly 1.
4
1 2 3 4 -> empty
1
1 3
1 4
2
2 4
3
4
1 2 is out because 2 minus 1 is 1. 1 3 is in, because 2 is not chosen and
the rule is about the chosen values only.
## What most people try first
Build the whole powerset, then test each selection by scanning its values for a
neighbouring pair. That works and it tests the same thing over and over: every
selection that contains 1 2 gets rebuilt and rejected once for each of the
2^(n-2) ways of filling in the rest.
The fix is the ordinary one for this shape of constraint. The rule only involves the value just added and the one before it, so it can be checked at the moment of the push, and a rejected push prunes everything below it.
## The method
Sort, then extend with any later index whose value is not exactly one more than the last value chosen:
go(i):
record cur
for j in i .. n-1:
if cur is not empty and a[j] - last(cur) == 1: continue
cur.push(a[j]); go(j + 1); cur.pop()
Here it is continue rather than break, and that difference is worth
noticing. In a total-under-a-limit search, failing once means failing for every
later value, so the loop can stop. Here it does not: from last value 3, the
value 4 is forbidden and 5 is fine. The constraint is not monotone in j, so
only this one branch dies.
## Why it is correct
Because the values are sorted and j ascends, cur is always increasing, so
the only pair that can differ by 1 is a pair of NEIGHBOURS inside cur. Every
neighbouring pair is tested exactly once, at the moment the later of the two is
pushed. So a selection survives to be recorded precisely when no neighbouring
pair differs by 1, which is precisely when no pair at all does.
That argument is the reason sorting is not optional. Unsorted, two chosen values
differing by 1 could sit far apart in cur and never be compared.
## The output convention, shared by every problem in this block
Values inside one selection are separated by single spaces and printed in
increasing order. Selections are printed one per line. Two selections are
ordered by comparing them position by position NUMERICALLY, and when one is a
prefix of the other the shorter one comes first, so the empty selection is
always first. The empty selection prints as the word empty. If there are no
selections at all, print none.
The empty selection always qualifies, so none is never printed.
## Cost
Proportional to the number of answers. For the values 1 .. n the count is the
(n+2)th Fibonacci number, so at n = 18 there are 6765 lines rather than the
262144 the powerset would build.
Constraints - `1 ≤ n ≤ 18` - `-1000 ≤ a[i] ≤ 1000` - All values are distinct.
Input
The first line contains an integer n.
The second line contains n space-separated distinct integers.
Output
Print every qualifying selection on its own line, values in increasing order separated by single spaces, the lines ordered as described. The empty selection prints as empty.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.