Q20: How do you generate all Subsets (Power Set) of a set of unique integers using Backtracking?

Use Backtracking to build decision trees. At each recursive index step, append current tempList state to result. Loop from start index to end of array: append nums[i] to tempList, recurse backtrack(i + 1), and remove last element (tempList.remove(tempList.size() - 1)) to backtrack.

Subsets Backtracking Solution

import java.util.*;

public class Subsets {
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), nums, 0);
        return result;
    }
    private static void backtrack(List<List<Integer>> result, List<Integer> temp, int[] nums, int start) {
        result.add(new ArrayList<>(temp));
        for (int i = start; i < nums.length; i++) {
            temp.add(nums[i]);
            backtrack(result, temp, nums, i + 1);
            temp.remove(temp.size() - 1); // Backtrack
        }
    }
}

💡 Appends subset states to result and backtracks choices step-by-step.

Key Takeaways

Generates $2^n$ unique subset combinations.
Backtracking template: Add element -> Recurse -> Remove element.

Knowledge Check

How many total subsets are generated for an input set containing N distinct elements?

Q20: How do you generate all Subsets (Power Set) of a set of unique integers using Backtracking?

STAY UPDATED WITH BYTES!