> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/1-100/subsets.md).

# 78. Subsets

### Description

Given a set of **distinct** integers, *nums*, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

### **Constraints**

### **Approach**

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/subsets)
* ProgramCreek
* YouTube

### Examples

{% tabs %}
{% tab title="Example 1" %}
**Input:** nums = \[1, 2, 3]

**Output:** \[ \[], \[1], \[2], \[3], \[1, 2], \[1, 3], \[2, 3], \[1, 2, 3] ]
{% endtab %}
{% endtabs %}

### Solutions

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(N×2^N) to generate all subsets and then copy 
 *    them into output list.
 * Space complexity : O(N×2^N) to keep all the subsets of length N, 
 *    since each of N elements could be present or absent.
 */

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> resultList = new ArrayList<>();
        for(int k = 0; k <= nums.length; k++) {
            backtrack(resultList, new LinkedList<Integer>(), nums, 0, k);
        }
        return resultList;
    }
    private void backtrack(
        List<List<Integer>> resultList,
        LinkedList<Integer> currList,
        int[] nums,
        int start,
        int k
    ) {
        if(k == 0) {
            resultList.add(new ArrayList(currList));
        }
        for(int i = start; i < nums.length; i++) {
            currList.add(nums[i]);
            backtrack(resultList, currList, nums, i+1, k-1);
            currList.removeLast();
        }
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*