Subsets

Generate every subset of a set. Each element is either in or out, so there are 2ⁿ of them.

Time O(n · 2ⁿ)Space O(n)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Build subsets one element at a time. Record the current path, then for each remaining element: add it, recurse on what comes after it, and take it back out.

Code

C++PythonC#

void subsets(const vector<int>& a, int start, vector<int>& path, vector<vector<int>>& result) {
    result.push_back(path);
    for (int i = start; i < (int)a.size(); i++) {
        path.push_back(a[i]);
        subsets(a, i + 1, path, result);
        path.pop_back();
    }
}

def subsets(a: list[int], start: int, path: list[int], result: list[list[int]]) -> None:
    result.append(path[:])
    for i in range(start, len(a)):
        path.append(a[i])
        subsets(a, i + 1, path, result)
        path.pop()

public static void Subsets(int[] a, int start, List<int> path, List<List<int>> result) {
    result.Add(new List<int>(path));
    for (int i = start; i < a.Length; i++) {
        path.Add(a[i]);
        Subsets(a, i + 1, path, result);
        path.RemoveAt(path.Count - 1);
    }
}

Tips

Choose, explore, un-choose. Every backtracking solution has those three lines.
Starting the loop at "start" stops the same subset from being built in a different order.

In the .NET library

new List<int>(path) copies the list. Adding path itself would store one shared reference, and every result would end up empty.