Top 25 Recursion and Backtracking Interview Questions (2026)

1. Introduction to Recursion & Backtracking

Recursion and Backtracking allow you to explore search spaces and combinations. Below are 25 essential questions with complete solutions in C++, Java, Python, and JavaScript.

2. Core Backtracking Questions

Q1. Generate All Subsets (Power Set)

cpp
vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> curr;
    function<void(int)> dfs = [&](int idx) {
        if (idx == nums.size()) { res.push_back(curr); return; }
        curr.push_back(nums[idx]);
        dfs(idx + 1);
        curr.pop_back();
        dfs(idx + 1);
    };
    dfs(0);
    return res;
}

java
public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    dfs(0, nums, new ArrayList<>(), res);
    return res;
}
private void dfs(int idx, int[] nums, List<Integer> curr, List<List<Integer>> res) {
    if (idx == nums.length) { res.add(new ArrayList<>(curr)); return; }
    curr.add(nums[idx]);
    dfs(idx + 1, nums, curr, res);
    curr.remove(curr.size() - 1);
    dfs(idx + 1, nums, curr, res);
}

python
def subsets(nums: list) -> list:
    res = []
    def dfs(idx, curr):
        if idx == len(nums):
            res.append(curr[:])
            return
        curr.append(nums[idx])
        dfs(idx + 1, curr)
        curr.pop()
        dfs(idx + 1, curr)
    dfs(0, [])
    return res

javascript
function subsets(nums) {
    let res = [];
    function dfs(idx, curr) {
        if (idx === nums.length) {
            res.push([...curr]);
            return;
        }
        curr.push(nums[idx]);
        dfs(idx + 1, curr);
        curr.pop();
        dfs(idx + 1, curr);
    }
    dfs(0, []);
    return res;
}

Time Complexity: O(n x 2^n) | Space Complexity: O(n)

3. Summary Table

Practice all recursion problems on DSAMaster's practice platform.