Missing undo step on backtrack
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.
Move from brute-force thinking to an efficient approach using backtracking strategy.
Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].
You may return the answer in any order.
Example 1:
Input: n = 4, k = 2 Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] Explanation: There are 4 choose 2 = 6 total combinations. Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.
Example 2:
Input: n = 1, k = 1 Output: [[1]] Explanation: There is 1 choose 1 = 1 total combination.
Constraints:
1 <= n <= 201 <= k <= nProblem summary: Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n]. You may return the answer in any order.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Backtracking
4 2
1 1
combination-sum)permutations)import java.util.*;
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> ans = new ArrayList<>();
backtrack(1, n, k, new ArrayList<>(), ans);
return ans;
}
private void backtrack(int start, int n, int k, List<Integer> cur, List<List<Integer>> ans) {
if (cur.size() == k) {
ans.add(new ArrayList<>(cur));
return;
}
// Prune: enough numbers must remain to fill the combination.
for (int x = start; x <= n - (k - cur.size()) + 1; x++) {
cur.add(x);
backtrack(x + 1, n, k, cur, ans);
cur.remove(cur.size() - 1);
}
}
}
func combine(n int, k int) [][]int {
ans := [][]int{}
cur := []int{}
var backtrack func(start int)
backtrack = func(start int) {
if len(cur) == k {
copyCur := append([]int{}, cur...)
ans = append(ans, copyCur)
return
}
for x := start; x <= n-(k-len(cur))+1; x++ {
cur = append(cur, x)
backtrack(x + 1)
cur = cur[:len(cur)-1]
}
}
backtrack(1)
return ans
}
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
ans: List[List[int]] = []
cur: List[int] = []
def backtrack(start: int) -> None:
if len(cur) == k:
ans.append(cur[:])
return
for x in range(start, n - (k - len(cur)) + 2):
cur.append(x)
backtrack(x + 1)
cur.pop()
backtrack(1)
return ans
impl Solution {
pub fn combine(n: i32, k: i32) -> Vec<Vec<i32>> {
let mut ans = Vec::new();
let mut cur = Vec::new();
fn backtrack(start: i32, n: i32, k: i32, cur: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {
if cur.len() as i32 == k {
ans.push(cur.clone());
return;
}
let upper = n - (k - cur.len() as i32) + 1;
for x in start..=upper {
cur.push(x);
backtrack(x + 1, n, k, cur, ans);
cur.pop();
}
}
backtrack(1, n, k, &mut cur, &mut ans);
ans
}
}
function combine(n: number, k: number): number[][] {
const ans: number[][] = [];
const cur: number[] = [];
const backtrack = (start: number): void => {
if (cur.length === k) {
ans.push([...cur]);
return;
}
for (let x = start; x <= n - (k - cur.length) + 1; x++) {
cur.push(x);
backtrack(x + 1);
cur.pop();
}
};
backtrack(1);
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Generate every possible combination without any filtering. At each of n positions we choose from up to n options, giving nⁿ total candidates. Each candidate takes O(n) to validate. No pruning means we waste time on clearly invalid partial solutions.
Backtracking explores a decision tree, but prunes branches that violate constraints early. Worst case is still factorial or exponential, but pruning dramatically reduces the constant factor in practice. Space is the recursion depth (usually O(n) for n-level decisions).
Review these before coding to avoid predictable interview regressions.
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.