1159. Selections Whose Total Divides Evenly
Given n distinct positive integers and a divisor m, print every selection
whose total is a multiple of m.
3 3
1 2 3 -> empty total 0, and 0 is a multiple of 3
1 2 total 3
1 2 3 total 6
3 total 3
The empty selection totals 0, and 0 is a multiple of every m, so the first
line is always empty and the output is never none. That is settled here
rather than left to the reader, because "is 0 divisible by 3" is the single most
common disagreement about this question.
## What most people try first
Enumerate every selection, add up each one, and keep the ones whose total is
divisible. That is correct, and the wasteful part is adding up the selection from
scratch at every node: a selection of length L costs O(L) to total, and its
2^(n-L) descendants each pay the same again.
## The method
Carry the running total down the recursion and test it on arrival. One addition per step replaces a full pass per node.
go(i, tot):
if tot mod m == 0: record cur
for j in i .. n-1:
cur.push(a[j]); go(j + 1, tot + a[j]); cur.pop()
Note what this problem deliberately does NOT have: a pruning rule. Divisibility
is not monotone. A total of 4 with m = 3 is not divisible and adding 2 makes it
divisible, so no branch can be cut on the strength of the current total alone,
and the search really does visit all 2^n nodes. Recognising when a constraint
cannot be pruned is as much a part of this technique as pruning when it can,
because a wrong prune here would silently drop answers rather than slow anything
down.
## Why it is correct
tot at any node equals the total of cur, because it starts at 0 and every
push adds exactly the value pushed while every undo returns to the caller's
value. So the test at the top of the call is a test on the selection the node
represents. Each selection is represented by exactly one node, by the argument
in problem 1152, so each qualifying selection is recorded exactly once.
## 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.
## Overflow
Values reach 100000 and n reaches 18, so a total reaches 1.8 * 10^6. That
is far inside the 2147483647 top of a signed 32 bit integer, so nothing here
overflows and the running total needs no special type. Carrying the total modulo
m instead would also work and is unnecessary at this size.
## Cost
O(2^n) nodes with O(1) work each, plus O(n) to print each qualifying line.
At n = 18 that is 262144 nodes however few of them qualify, which is the price
of a constraint that cannot be pruned.
Constraints - `1 ≤ n ≤ 18` - `1 ≤ m ≤ 100000` - `1 ≤ a[i] ≤ 100000` - All values are distinct.
Input
The first line contains two integers n and m.
The second line contains n space-separated distinct positive integers.
Output
Print every selection whose total is a multiple of m on its own line, values in increasing order separated by single spaces, the lines ordered as described. The empty selection totals 0 and always qualifies, printing as empty.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.