219. How Many Subsets
Core1000 ms256 MBSolved by 0%
A set has n distinct elements. Print how many subsets it has, counting both
the empty set and the set itself.
Think about it one element at a time. For each element you make an independent choice: in or out. That is the shape of every backtracking problem you will meet, and here you only have to count the leaves rather than list them.
Read the constraint. At n = 62 there are more subsets than you could ever
generate, so this is a counting problem rather than a generating one.
Constraints - `0 ≤ n ≤ 62`
Input
A single line containing one integer n.
Output
Print one integer, the number of subsets.
Input3
Output8
Noteis a set of three, which has eight subsets
Input0
Output1
Noteis the empty set, which still has one subset: itself
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.