PPractick

The problem

A puzzle app generates "killer sudoku" cage hints: a cage of k cells must contain distinct digits from 1 to 9 that add up to n. For each cage, the hint panel lists every possible digit set. The search space is tiny (subsets of 1–9), but it's a clean backtracking exercise: choose digits in increasing order so each set appears once, and stop as soon as the set is full or the remaining sum can't be reached.

Example: k = 3, n = 9 → [1,2,6] [1,3,5] [2,3,4].

Function signature

vector<vector<int>> combinationSum3(int k, int n);  // lexicographic order

Test cases

Input (k, n)	Output	Explanation
(3, 7)	[1,2,4]	The only set
(3, 9)	[1,2,6] [1,3,5] [2,3,4]
(4, 1)	(none)	The smallest 4 digits already sum to 10
(2, 18)	(none)	The largest pair is 8 + 9 = 17
(9, 45)	[1,2,3,4,5,6,7,8,9]	All nine digits

(Confirm: only digits 1–9, each at most once per combination; combinations are sets, output in lexicographic order.)

How interviewers phrase it

• "Find all valid combinations of k numbers that sum up to n, using only numbers 1 through 9, each at most once" (LeetCode 216).

Clarifying questions to ask

1. Can a digit repeat within a combination? (No.)
2. Must the combination have exactly k numbers? (Yes.)
3. Does order matter? (No, so [1,2,4] and [2,1,4] are the same.)

Follow-ups to expect

1. "How do you avoid duplicate sets?"
2. "What pruning helps?"
3. "What's the worst-case size of the search?"
4. "Could you use bitmasks instead?"
5. "Complexity?"

Related questions

• Generate Binary Strings Without Consecutive 1s Medium
• Generate Parentheses Medium
• Power Set Medium
• Combination Sum Medium
• Combination Sum II Medium
• Subsets I Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in