Course4all
Join us on telegram
Home/dsa/Backtracking/Subsets

Subsets

Master this topic with zero to advance depth.

Subsets

The Power Set

A power set of SS is the set of all subsets of SS, including the empty set and SS itself. For a set with nn elements, there are 2n2^n subsets.

Inclusion-Exclusion Principle

At each step, we have two choices for the current element: either include it in the current subset or exclude it.

Generate all possible subsets (the power set) of a set of unique integers. Includes visual inclusion-exclusion trace.

Medium

Examples

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Approach 1

Level I: Recursive Backtracking (Include/Exclude)

Intuition

At each step, we decide whether to add nums[i] to our subset or not.

Use a recursive function dfs(idx, current). In one branch, add nums[idx] and recurse. In the other, don't add it and recurse.

⏱ O(N * 2^N)💾 O(N) for recursion stack.

Detailed Dry Run

Dry Run: nums=[1,2] | idx | path | Decision | Next State | | :-- | :---: | :--- | :--- | | 0 | [] | Include 1| DFS(1, [1])| | 1 | [1] | Include 2| DFS(2, [1,2]) -> RES: [1,2]| | 1 | [1] | Exclude 2| DFS(2, [1]) -> RES: [1]| | 0 | [] | Exclude 1| DFS(1, []) | | 1 | [] | Include 2| DFS(2, [2]) -> RES: [2]| | 1 | [] | Exclude 2| DFS(2, []) -> RES: []|
java
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(0, new ArrayList<>(), nums, res);
        return res;
    }
    private void backtrack(int idx, List<Integer> current, int[] nums, List<List<Integer>> res) {
        if (idx == nums.length) {
            res.add(new ArrayList<>(current));
            return;
        }
        current.add(nums[idx]);
        backtrack(idx + 1, current, nums, res);
        current.remove(current.size() - 1);
        backtrack(idx + 1, current, nums, res);
    }
}
Approach 2

Level II: Cascading (Iterative Generation)

Intuition

Start with an empty set and gradually build the power set.

Start with [[]]. For each number in nums, duplicate all existing subsets and add the current number to the duplicates.

⏱ O(N * 2^N)💾 O(N * 2^N) to store subsets.

Detailed Dry Run

nums=[1,2]

  1. res = [[]]
  2. num=1: res = [[], [1]]
  3. num=2: res = [[], [1], [2], [1,2]]
java
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        for (int n : nums) {
            int size = res.size();
            for (int i = 0; i < size; i++) {
                List<Integer> subset = new ArrayList<>(res.get(i));
                subset.add(n);
                res.add(subset);
            }
        }
        return res;
    }
}
Approach 3

Level III: Bit Manipulation (Bitmask)

Intuition

Each subset of a set with NN elements can be uniquely mapped to a binary number from 00 to 2N−12^N - 1.

Loop from i = 0 to 2^N - 1. For each i, if the jj-th bit is 1, include nums[j] in the current subset.

⏱ O(N * 2^N)💾 O(N * 2^N)

Detailed Dry Run

nums=[1,2]

  • i=0 (00): []
  • i=1 (01): [1]
  • i=2 (10): [2]
  • i=3 (11): [1,2]
java
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < (1 << n); i++) {
            List<Integer> subset = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0) subset.add(nums[j]);
            }
            res.add(subset);
        }
        return res;
    }
}
← Previous QuestionPermutations
Next Question →Subsets II