Subsets

Key Signals & Indicators

• Need to evaluate all possible groupings (combinations/power set)
• Ordering does not matter in output sets
• Small input sizes (usually n <= 20) allowing O(2^n) complexity

// C++ Backtracking Subsets Template
#include <vector>

void backtrack(int start, const std::vector<int>& nums, std::vector<int>& current, std::vector<std::vector<int>>& subsets) {
    subsets.push_back(current); // Process state
    
    for (size_t i = start; i < nums.size(); ++i) {
        current.push_back(nums[i]); // Choose
        backtrack(i + 1, nums, current, subsets); // Recurse
        current.pop_back(); // Backtrack / Undo
    }
}

std::vector<std::vector<int>> getSubsets(const std::vector<int>& nums) {
    std::vector<std::vector<int>> subsets;
    std::vector<int> current;
    backtrack(0, nums, current, subsets);
    return subsets;
}