Run it in your head. What does this return?

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Subsets

Medium

Every node of the tree is a subset

In simple words

For each item, branch into 'take it' and 'leave it' to build every possible group.

The idea

At each index decide to include or skip that element. The recursion tree's leaves — and in fact every node — correspond to a distinct subset.

←→stepspaceplay

1/10

Optimal

timeO(n·2ⁿ)spaceO(n)

Branch on each element.

1function dfs(i, path) {2  if (i === n) { out.push([...path]); return; }3  dfs(i + 1, path);          // exclude4  path.push(nums[i]);5  dfs(i + 1, path);          // include6  path.pop();7}

Input

array: [1, 2, 3]

Memory

subset: —

Output

count: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: nums = [1, 2, 3]
Output:: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
Explanation:: All 2^3 = 8 subsets.

Example 2

Input:: nums = [1, 2]
Output:: [[], [1], [2], [1, 2]]
Explanation:: 4 subsets including the empty set.

Example 3

Input:: nums = [0]
Output:: [[], [0]]
Explanation:: Just {} and {0}.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.