> For the complete documentation index, see [llms.txt](https://docs-57.gitbook.io/data-structure-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs-57.gitbook.io/data-structure-and-algorithms/problems/backtracking/subsets.md).

# Subsets

Given an integer array `nums` of **unique** elements, return *all possible* 

*subsets* *(the power set)*.

The solution set **must not** contain duplicate subsets. Return the solution in **any order**.

 

**Example 1:**

<pre><code><strong>Input: nums = [1,2,3]
</strong><strong>Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [0]
</strong><strong>Output: [[],[0]]
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= nums.length <= 10`
* `-10 <= nums[i] <= 10`
* All the numbers of `nums` are **unique**.

**Problem Statement:** Imagine you have a box of unique toys. You want to see all the different ways you can pick some toys from the box. You can pick all the toys, some of the toys, or none at all. Each different selection of toys is called a subset.

For example, if your box has 3 toys labeled 1, 2, and 3, the different subsets you can make are: no toys (`[]`), just toy 1 (`[1]`), just toy 2 (`[2]`), just toy 3 (`[3]`), toys 1 and 2 (`[1,2]`), toys 1 and 3 (`[1,3]`), toys 2 and 3 (`[2,3]`), and all toys (`[1,2,3]`).

**Solution Explanation:** The solution uses a method called recursion, which is like a loop but can “branch out” into multiple smaller loops.

It starts with no toys (`[]`) as the first subset. Then, for each toy in the box, it creates new subsets by adding that toy to all existing subsets. It does this by “branching out” into two possibilities at each step: one where it adds the current toy to the subset, and one where it doesn’t. It keeps doing this until it has tried all toys in the box.

Here’s how it works step-by-step for the box of toys `[1,2,3]`:

1. Start with no toys: `[[]]`
2. Try adding the first toy (1):
   * Keep the original subset without toy 1: `[[]]`
   * Add a new subset with toy 1: `[[1]]`
3. Try adding the second toy (2):
   * Keep the original subsets without toy 2: `[[], [1]]`
   * Add new subsets with toy 2: `[[2], [1,2]]`
4. Try adding the third toy (3):
   * Keep the original subsets without toy 3: `[[], [1], [2], [1,2]]`
   * Add new subsets with toy 3: `[[3], [1,3], [2,3], [1,2,3]]`

So the final subsets are: `[[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]`.

```csharp
public class Solution {
    public IList<IList<int>> Subsets(int[] nums) {
        IList<IList<int>> result = new List<IList<int>>();
        GenerateSubsets(nums, 0, new List<int>(), result);
        return result;
    }

    private void GenerateSubsets(int[] nums, int index, List<int> current, IList<IList<int>> result) {
        result.Add(new List<int>(current));
        for (int i = index; i < nums.Length; i++) {
            current.Add(nums[i]);
            GenerateSubsets(nums, i + 1, current, result);
            current.RemoveAt(current.Count - 1);
        }
    }
}

```

The time and space complexity of the algorithm is as follows:

**Time Complexity:** The time complexity is O(N \* 2^N), where N is the number of elements in the input array. This is because, for each element, the algorithm branches into two recursive calls (one including the element in the subset and one excluding it), leading to 2^N possible subsets. For each subset, it takes O(N) time to make a copy of it (using `new List<int>(current)`) and add it to the result list.

**Space Complexity:** The space complexity is also O(N \* 2^N). This is because there are 2^N possible subsets and each subset can take up to N space. The space is used to store the subsets in the result list and the recursive call stack.

Please note that these complexities are approximate and actual performance can vary depending on the specifics of the input and the runtime environment. Also, these complexities assume that the `List.Add` operation is O(1), which is generally the case in most environments but could vary. If this operation is not O(1), the time and space complexity could be higher.


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://docs-57.gitbook.io/data-structure-and-algorithms/problems/backtracking/subsets.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.