Single-Digit Sum Sets

MediumBacktracking

Problem

A puzzle cage in a number game holds exactly k cells and must sum to n. Each cell holds a digit from 1 to 9, and no digit may repeat inside the cage.

Return every set of k distinct digits that sums to n, in any order.

Example 1

Input:
k = 3, n = 9
Output:
[[1, 2, 6], [1, 3, 5], [2, 3, 4]]

These are the only three sets of three distinct digits adding to 9.

Example 2

Input:
k = 3, n = 7
Output:
[[1, 2, 4]]

Constraints

  • 1 ≤ k ≤ 9
  • 1 ≤ n ≤ 60

Hint

Show the first hint

Pick digits in increasing order so each set is produced once.

Walkthrough

How to approach it

01Clarify before coding

  • Can a digit repeat in a cage? No.
  • Is 0 allowed? No, digits are 1–9.
  • Is the order inside a set meaningful? No, sets.

02Brute force

Enumerate all 2^9 = 512 subsets of 1..9 and keep those with size k and sum n.

Cost: O(9 · 2^9), trivially fast; the interviewer wants the pruned backtracking because it generalises to larger digit ranges.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.