Backtracking Permutations and Subsets

Opening scenario

Letter Combinations of a Phone Number (LC 17): given digits 2–9, return every string formable by mapping each digit to its phone letters (2→abc, …). Follow-up you should expect: N-Queens (LC 51) — place n queens on an n×n board so none attack each other; return all distinct solutions.

For the phone problem, choose one letter per digit in the original digit order; an empty input returns [], and 0/1 are not allowed. For N-Queens, queens attack along rows, columns, and diagonals; each returned board has n strings using Q and .. Start by considering which choices remain after placing the first letter or queen. LC numbers identify LeetCode problems.

Question progression

Q1 — Phone letters: how do you generate every combination without nested loops?

Question: With k digits you'd need k nested loops — but k is only known at runtime. How do you enumerate all combinations when the loop depth is dynamic?