Subsets & Combinations

Many problems ask for all subsets of a set or all combinations of size k. Both can be solved with DFS backtracking: at each step, you either include or exclude the current element (or choose which element to place next), and recurse.

Subsets (Power Set)

Generate all subsets of an array (order of elements in a subset doesn’t matter; no duplicates if input has no duplicates).

Idea: For each index i, either include nums[i] in the current path or skip it. After processing all indices, record the current path as a subset.

JavaCopy
void dfs(int[] nums, int i, List<Integer> path, List<List<Integer>> result) {
    if (i == nums.length) {
        result.add(new ArrayList<>(path));
        return;
    }
    path.add(nums[i]);
    dfs(nums, i + 1, path, result);
    path.remove(path.size() - 1);
    dfs(nums, i + 1, path, result);
}

Time O(2^n), space O(n) recursion.

Combinations (Choose k)

Generate all combinations of size k from [1..n] (or from an array).

Idea: Build a path of length k. At each step, choose the next number from a starting index (e.g. start) so you only pick larger indices and avoid duplicate combinations.

JavaCopy
void dfs(int n, int k, int start, List<Integer> path, List<List<Integer>> result) {
    if (path.size() == k) {
        result.add(new ArrayList<>(path));
        return;
    }
    for (int i = start; i <= n; i++) {
        path.add(i);
        dfs(n, k, i + 1, path, result);
        path.remove(path.size() - 1);
    }
}

Subsets with Duplicates

If the array has duplicates, sort it and when iterating, skip recursing on the same value at the same “level” (only the first occurrence at that level is used for the branch).

Summary

Subsets: include/skip each element. Combinations: choose the next element from a starting index and recurse with a larger start so combinations are built in one order and duplicates are avoided. Both use O(2^n) or C(n,k) time and O(n) space for the path.