# Subsets

Given a set of distinct integers, return all possible subsets.

## Example

If S = \[1,2,3], a solution is:

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

## Solution

这道题是典型的隐式图题型，这种题的技巧就是可以画出DFS的便利树，与Permutations 的区别就是，它是每个节点都需要纪录进入结果数组，而后者是最后一层纪录进入。

```
class Solution:
    """
    @param S: The set of numbers.
    @return: A list of lists. See example.
    """
    def subsets(self, nums):
        # write your code here
        if nums == None:
            return []
        result = []
        nums.sort()
        self.dfs(nums, result, [], 0)
        return result 
    def dfs(self, nums, result, current, pos):
        result.append(list(current))
        for i in range(pos, len(nums)):
            current. append(nums[i])
            self.dfs(nums, result, current, i + 1)
            del current[-1]
```

```
public class Solution {
    public IList<IList<int>> Subsets(int[] nums) {
        Array.Sort(nums);
        IList<IList<int>> result = new List<IList<int>>();
        List<int> current = new List<int>();
        DFS(nums, result, current, 0);

        return result;
    }

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

    }
}
```

```
public class Solution {
    public IList<IList<int>> SubsetsWithDup(int[] nums) {
        Array.Sort(nums);
        IList<IList<int>> result = new List<IList<int>>();
        List<int> current = new List<int>();
        DFS(nums, result, current, 0);
        return result;
    }

    public void DFS(int[] nums, IList<IList<int>> result, List<int> current, int pos){
        result.Add(new List<int>(current));
        for(int i= pos; i < nums.Length; i++){
            if(i > 0 && nums[i] == nums[i - 1] && i > pos){
                continue;
            }
            current.Add(nums[i]);
            DFS(nums, result, current, i + 1);
            current.RemoveAt(current.Count - 1);
        }
    }
}
```


---

# Agent Instructions: 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://liuxue2010.gitbook.io/data-structure-and-algorithms/graph/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.