Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Count the ways to write X as a sum of **unique** natural numbers each raised to the power N (e.g. 100 = 10² = 6²+8² = 1²+3²+4²+5²+7² → 3 ways). Recurse over candidate bases in increasing order with an include/exclude choice: at base `b`, either use `b^N` (subtract it and move to `b+1`) or skip `b` (move to `b+1`). Base cases: if `b^N == remaining` count 1, if `b^N > remaining` count 0. Uniqueness is free because each base is considered exactly once and the base only increases. Time is O(2^m) where m = ⌊X^(1/N)⌋ bases.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you model 'sum of unique powers equal to X' as an include/exclude recursion over an increasing base, with correct exact-hit and overflow base cases, and recognise that advancing the base enforces uniqueness.
Where candidates slip
Allowing a base to be reused (not advancing in the include branch), restarting the base from 1 each call (producing permutations / duplicates), or wrong base cases (e.g. continuing after `base^N > remaining`).
How to stand out
State that the base monotonically increases so each natural appears at most once, prune the moment `base^N > remaining`, and note this is subset-sum's count variant — mention memoization on (remaining, base) if the bounds grew.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewCount ways X = sum of unique b^NReuse a base?Yes (unlimited)No (unique)Explore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Subset Enumeration over Bases
1Hint 1Explore hintHide hint
List the candidate powers: 1^N, 2^N, …, up to the largest base whose power is ≤ X. Call the count m.
2Hint 2Explore hintHide hint
Every representation is a subset of those m powers, so enumerate all 2^m subsets (e.g. via bitmasks).
3Hint 3Explore hintHide hint
For each subset, sum its powers and increment the count when the sum equals X. Since each power appears once per subset, uniqueness is automatic.
A · Core idea
Make the 'subset of powers' framing literal. First build the candidate list [1^N, 2^N, …, k^N] where k^N ≤ X < (k+1)^N. Each valid representation is some subset of this list whose elements add up to X, so iterate over all 2^m subsets and count the ones that hit X exactly.
Why uniqueness is free. A subset contains each candidate at most once by definition, so we never reuse a base. And because a subset is unordered, we never double-count {1², 3²} and {3², 1²}. The two problem constraints fall out of the subset model.
Why it's only a stepping stone. Enumerating all 2^m subsets wastes work: once a partial sum exceeds X, every superset that keeps those elements also exceeds X, yet the bitmask enumeration still visits them. The recursive include/exclude version prunes those branches the instant base^N > remaining, which is why it's preferred — but the subset view is the cleanest way to see what we're counting.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
X = 10, N = 2Interactive diagram
Subsets of {1,4,9} for X=10
{}Only {1,9} sums to 10. The bitmask enumerates all eight subsets.
1C · Code with teaching comments
Reference implementation previewpublic int powerSum(int X, int N) { java.util.List<Integer> powers = new java.util.ArrayList<>(); for (int b = 1; Math.pow(b, N) <= X; b++) powers.add((int) Math.pow(b, N)); int m = powers.size(), count = 0; for (int mask = 0; mask < (1 << m); mask++) {Explore the full codeHide the full code
D · Why it works and complexityO(2^m · m) timeO(m) spaceOpen the invariant and proofExplore the proofHide the proof
Whenever a problem says 'unique elements, order irrelevant, hit a target', it's subset-sum. Enumerating subsets is the brute baseline; pruned recursion is the same enumeration that stops early.
ComplexityO(2^m · m) time, O(m) space — There are m ≈ ⌊X^(1/N)⌋ candidate powers, 2^m subsets, and summing a subset costs O(m), giving O(2^m · m). The candidate list is O(m) space.
E · Edge cases and pitfalls3Including powers larger than X in the candidate list — wasteful, though they never contribute.Explore edge casesHide edge cases
Pitfalls
- Including powers larger than X in the candidate list — wasteful, though they never contribute.
- Integer overflow if X were large and N small — fine here (X ≤ 1000).
- Visiting all 2^m subsets even after a partial sum exceeds X — no early pruning.
Approach 2 of 2 · Optimal
Include/Exclude Recursion with Increasing Base (Optimal)
1Hint 1Explore hintHide hint
Recurse on `(remaining, base)`. Compute `p = base^N`. If `p == remaining` you've landed exactly on a representation → return 1. If `p > remaining`, no larger base helps → return 0 (prune).
2Hint 2Explore hintHide hint
Otherwise make the two choices: **include** `base^N` (recurse with `remaining - p, base + 1`) plus **exclude** it (recurse with `remaining, base + 1`). Sum them.
3Hint 3Explore hintHide hint
Always pass `base + 1` so each natural is offered exactly once — that's uniqueness. Start at `ways(X, 1)`.
A · Core idea
Frame the search as a sequence of independent yes/no decisions, one per candidate base, taken in increasing order.
The recursion. State is (remaining, base): how much of X is left, and the smallest base we're still allowed to use. Compute p = base^N.
- If
p == remaining, using this base exactly finishes a representation → 1 way. - If
p > remaining, this base already overshoots, and every later base is larger, so nothing from here on can work → 0 ways (this prune is what keeps it fast). - Otherwise we have a genuine choice: include
base^N(subtract it, advance tobase + 1) or exclude it (keepremaining, advance tobase + 1). The total is the sum of both subtrees.
Why advancing the base enforces uniqueness. Both branches recurse with base + 1, never base. So a base, once considered, is never offered again — each natural is used at most once. And because we only ever move forward, the combination {1, 3} is discovered as 'include 1, skip 2, include 3', never as 'include 3, then 1'. That single rule gives us both 'unique' and 'order doesn't matter' for free.
Why we count instead of collect. The problem asks only how many representations exist, so each leaf contributes 0 or 1 and we just add. No path array, no copying — the function returns an int. If the prompt asked for the actual subsets, we'd carry a list and snapshot it at the p == remaining leaf.
Why no memoization is needed here. With X ≤ 1000 and N ≥ 2, m = ⌊X^(1/N)⌋ is small (e.g. ≤ 31 for N = 2, X = 1000, and far fewer for larger N), and the overshoot prune cuts the tree hard, so plain recursion is comfortably fast. If the bounds grew, memoizing on (remaining, base) would make it pseudo-polynomial.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
X = 10, N = 2How to read it:Left edge = include base², right edge = exclude. The single ✓ leaf is 1² + 3².
1C · Code with teaching comments
D · Why it works and complexityO(2^m) timeO(m) spaceOpen the invariant and proofExplore the proofHide the proof
This is subset-sum's count form: take-it-or-leave-it over candidates, advancing the index so each is used once. The only domain-specific part is generating candidates as perfect powers and pruning when base^N overshoots. Recognise the shape and Subsets, Combination Sum, and Partition Equal Subset Sum are the same engine.
ComplexityO(2^m) time, O(m) space — The recursion branches in two at each base and the base ranges over m ≈ ⌊X^(1/N)⌋ values, so the tree has O(2^m) nodes; the `p > remaining` prune trims many. Each node does O(1) work (a power and a comparison). Recursion depth is O(m).
E · Edge cases and pitfalls6X = 1, N = 2 — ways(1,1): p = 1 == remaining → return 1. The single base 1 itself is a representation.Explore edge casesHide edge cases
Edge cases handled
X = 1, N = 2ways(1,1): p = 1 == remaining → return 1. The single base 1 itself is a representation.X = 2, N = 2ways(2,1): p=1<2 → ways(1,2)+ways(2,2). ways(1,2): p=4>1→0. ways(2,2): p=4>2→0. Total 0 — 2 isn't a sum of unique squares.X = 100, N = 2Returns 3: 10², 6²+8², and 1²+3²+4²+5²+7² are all found by the increasing-base search.
Pitfalls
- Recursing with `base` instead of `base + 1` in the include branch — allows reusing a base (e.g. 2²+2²).
- Restarting base from 1 each call — produces ordered duplicates and overcounts.
- Continuing the search after `base^N > remaining` instead of returning 0 — wasted work and possible miscount.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int powerSum(int X, int N) { return ways(X, 1, N); } private int ways(int remaining, int base, int N) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Allowing a base to be reused
If the include branch recurses with the same base instead of base + 1, the algorithm counts representations like 1² + 1² + … that reuse a natural, violating uniqueness.
Explore the code comparisonHide the code comparison
Allowing a base to be reused
If the include branch recurses with the same base instead of base + 1, the algorithm counts representations like 1² + 1² + … that reuse a natural, violating uniqueness.
Don't write this
return ways(remaining - p, base) + ways(remaining, base + 1) # base reused!Write this instead
return ways(remaining - p, base + 1) + ways(remaining, base + 1)2Restarting the base each call
Looping base from 1 inside every call discovers {1,3} as both '1 then 3' and '3 then 1', overcounting. Moving forward only counts each combination once.
Explore the code comparisonHide the code comparison
Restarting the base each call
Looping base from 1 inside every call discovers {1,3} as both '1 then 3' and '3 then 1', overcounting. Moving forward only counts each combination once.
Don't write this
int total = 0;
for (int b = 1; Math.pow(b, N) <= remaining; b++)
total += ways(remaining - (int)Math.pow(b, N), 1, N); // restarts at 1Write this instead
int total = 0;
for (int b = base; Math.pow(b, N) <= remaining; b++)
total += ways(remaining - (int)Math.pow(b, N), b + 1, N); // forward only3Missing the overshoot prune
Without `if (p > remaining) return 0`, the recursion keeps trying ever-larger bases that can never fit, doing pointless work and risking miscounts if the base case is mis-ordered.
Explore the code comparisonHide the code comparison
Missing the overshoot prune
Without `if (p > remaining) return 0`, the recursion keeps trying ever-larger bases that can never fit, doing pointless work and risking miscounts if the base case is mis-ordered.
Don't write this
if p == remaining:
return 1
# no prune — keeps recursing with bigger basesWrite this instead
if p > remaining:
return 0
if p == remaining:
return 1Revise
Carry the pattern into the interview
Pattern to remember
Increasing-base include/exclude recursion (each base used at most once)
Code pattern to memorize
def ways(remaining, base, N):
p = base ** N
if p > remaining: return 0 # base too big → dead end
if p == remaining: return 1 # exact hit → one way
# include base^N, or skip it — base always advances
return ways(remaining - p, base + 1, N) + ways(remaining, base + 1, N)Rules to remember
- 1Always advance the base (
base + 1) in both branches — that's what guarantees each natural is used at most once (uniqueness for free). - 2Two base cases:
base^N == remainingreturns 1 (found a combination);base^N > remainingreturns 0 (prune, since later bases are even larger). - 3Start the recursion at base = 1, remaining = X.
- 4The include branch subtracts
base^N; the exclude branch leavesremainingunchanged. Both then move tobase + 1. - 5You return a count, not the combinations themselves — no path array needed, just sum the two branches.
Use this pattern when
- Count subsets of a fixed candidate set that hit an exact target
- Each element usable at most once, order irrelevant (combinations, not permutations)
- Candidates are generated on the fly (here, perfect powers) and naturally bounded
- Classic include/exclude (take-it-or-leave-it) recursion
Choose another pattern when
- Elements may be reused unlimited times → don't advance the base in the include branch (that's coin-change style)
- You need the actual combinations, not just the count → carry a path and record at the exact-hit leaf
- Order matters / arrangements wanted → that's permutations, not this subset count
- X or the candidate count is large with overlapping subproblems → memoize on (remaining, base)
Interview takeaway
The Power Sum is the canonical include/exclude subset-sum recursion with one twist: candidates are perfect powers and the base only moves forward, so uniqueness comes for free. Master 'subtract-and-advance OR skip-and-advance' here and Subsets, Combination Sum, and Partition all reuse it.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternInclude/exclude subset-sum recursion: at each candidate, take it or leave it, advancing the index so each is used at most once. The overshoot prune and exact-hit base case keep it tight. Recognise it whenever you count subsets that hit a target — Combination Sum, Subsets, and Partition Equal Subset Sum share the engine.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Combination SumSame include/exclude shape, but candidates may be reused — don't advance the index on include.
- SubsetsEnumerate all subsets with a start index — the structure underlying this count.
- Partition Equal Subset SumComing soonSubset-sum to a fixed target — same recursion, often memoized into a DP.