Subsets [Medium] — Backtracking & Bit Manipulation

Problem Statement

Given an integer array of unique elements, return all possible subsets (the power set).

Input: [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Intuition

Backtracking: at each element, choose to include or not. Start index ensures we never go backwards.

Bitmask: for n elements, iterate 0 to 2^n−1; each bit decides inclusion.

Solutions

C++

// Backtracking
vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> res; vector<int> cur;
    function<void(int)> dfs = [&](int start) {
        res.push_back(cur);
        for (int i = start; i < nums.size(); i++) {
            cur.push_back(nums[i]); dfs(i+1); cur.pop_back();
        }
    };
    dfs(0);
    return res;
}

Java

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    dfs(nums, 0, new ArrayList<>(), res);
    return res;
}
void dfs(int[] nums, int start, List<Integer> cur, List<List<Integer>> res) {
    res.add(new ArrayList<>(cur));
    for (int i = start; i < nums.length; i++) {
        cur.add(nums[i]); dfs(nums, i+1, cur, res); cur.remove(cur.size()-1);
    }
}

JavaScript

var subsets = function(nums) {
    const res = [];
    function dfs(start, cur) {
        res.push([...cur]);
        for (let i = start; i < nums.length; i++) {
            cur.push(nums[i]); dfs(i+1, cur); cur.pop();
        }
    }
    dfs(0, []);
    return res;
};

Python

def subsets(nums: list[int]) -> list[list[int]]:
    res = []
    def dfs(start, path):
        res.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            dfs(i + 1, path)
            path.pop()
    dfs(0, [])
    return res

Python — Bitmask

def subsets_bitmask(nums: list[int]) -> list[list[int]]:
    n = len(nums)
    return [[nums[j] for j in range(n) if mask & (1 << j)]
            for mask in range(1 << n)]

Complexity

Time: O(2^n × n)
Space: O(n) stack