Generate All Subsets Backtracking Java | Fresher Interview

Direct Answer

Generate all 2^n subsets with backtracking: at each index you make a binary choice - include the current element or skip it - then recurse to the next index. Add a copy of the current subset at every node (or only at the leaves). It's O(2^n) subsets, each up to length n, so O(n * 2^n) total work. The choose/recurse/un-choose pattern drives it.

Deep Dive & Architecture

At each input position, a subset has two choices: include the value or skip it. Backtracking explores both branches while one mutable path stores the current subset.

Worked example: [1, 2]

Begin with the empty path and record []. Include 1 and record [1]; from there include 2 and record [1, 2]. Remove 2 to restore [1], then return and remove 1. The branch that skips 1 can now include 2 and record [2]. The complete power set is [], [1], [1, 2], [2].

A common loop-based form records the current path at every call and tries candidates from a start index onward. Passing i + 1 prevents the same array position from being chosen twice. Copy the path when adding it to the answer; storing the mutable list itself would make all result entries change during backtracking.

For n distinct items there are exactly 2^n subsets. Producing and copying them takes O(n × 2^n) time in the worst case, and the recursion path is O(n) deep, excluding output storage. If the input contains duplicates and unique subsets are required, sort first and skip equal values at the same recursion level.

Code Example

List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), result);
    return result;
}
void backtrack(int[] nums, int start, List<Integer> cur, List<List<Integer>> res) {
    res.add(new ArrayList<>(cur));            // COPY, not the reference
    for (int i = start; i < nums.length; i++) {
        cur.add(nums[i]);                     // choose
        backtrack(nums, i + 1, cur, res);     // explore
        cur.remove(cur.size() - 1);           // un-choose
    }
}

// nums = {1,2}: [] , [1], [1,2], [2]  -> 2^2 = 4 subsets

Common Mistakes & Pitfalls

• Adding the reference: res.add(cur) stores the live list - all entries become identical at the end. Add a copy.
• Forgetting un-choose: not removing the last element after recursion corrupts sibling branches.
• Wrong start index: recurse with i + 1 (not start + 1) to avoid duplicate subsets.
• Duplicates in input: sort and skip equal elements if the set may contain duplicates.