> For the complete documentation index, see [llms.txt](https://liuxue2010.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://liuxue2010.gitbook.io/data-structure-and-algorithms/graph/subsets.md).

# 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);
        }
    }
}
```