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:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:

Input: nums = [0]
Output: [[],[0]]

Approach

The most intuitive and scalable way to generate all subsets is through backtracking. This recursive method explores every decision point: whether to include or exclude the current element. For each index in the input array, we branch into two paths—one that includes the element and one that skips it.

A temporary list (commonly named subset) is used to build the current subset, and another list subsets collects all valid subsets. At every recursive call, once we reach the end of the input array, we add a copy of subset to subsets. This ensures that each possible combination is explored and recorded.

At every index we do the following:

# Consider the current element and add it to the current subset.
subset.append(nums[i])
self.findSubsets(i + 1, nums, subset, subsets)

# Backtrack: remove the current element so that we can explore
# the decision where this element is NOT included in the subset.
subset.pop()

# Skip the current element and move to the next index.
self.findSubsets(i + 1, nums, subset, subsets)

Here is the recursive tree that explains the above approach. Open it in a new tab to the see full recursive tree.

Aakash Verma

The channel is for anyone who wants to learn Computer Programming and build & grow career in IT industry. We’ll be talking about the following: ◉ Artificial Intelligence ◉ Problem Solving ◉ Data Structures and Algorithms ◉ OOPs, LLD, and System Design ◉ Interview Experiences & Preparatory Stuff ◉ Live Q & A with Industry Experts About Author: Aakash Verma Senior Software Engineer at Atlassian ex- Software Engineer at SingleStore, ShareChat & Moj

YouTube

Java Code

class Solution {

    private void findSubsets(int i, int[] nums, List<Integer> subset, List<List<Integer>> subsets) {
        if (i == nums.length) {
            subsets.add(new ArrayList<>(subset));
            return;
        }

        // Include nums[i]
        subset.add(nums[i]);
        findSubsets(i + 1, nums, subset, subsets);

        // Backtrack
        subset.remove(subset.size() - 1);

        // Exclude nums[i]
        findSubsets(i + 1, nums, subset, subsets);
    }

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> subsets = new ArrayList<>();
        List<Integer> subset = new ArrayList<>();

        findSubsets(0, nums, subset, subsets);

        return subsets;
    }
}

C++ Code

class Solution {
private:
    void findSubsets(int i, vector<int>& nums, vector<int>& subset, vector<vector<int>>& subsets) {

        if (i == nums.size()) {
            subsets.push_back(subset);
            return;
        }

        // Include nums[i]
        subset.push_back(nums[i]);
        findSubsets(i + 1, nums, subset, subsets);

        // Backtrack
        subset.pop_back();

        // Exclude nums[i]
        findSubsets(i + 1, nums, subset, subsets);
    }

public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> subsets;
        vector<int> subset;

        findSubsets(0, nums, subset, subsets);

        return subsets;
    }
};

Python Code

class Solution:

    def findSubsets(self, i, nums, subset, subsets):
        if i == len(nums):
            subsets.append(subset[:])
            return

        # Include nums[i]
        subset.append(nums[i])
        self.findSubsets(i + 1, nums, subset, subsets)
        
        # Backtrack
        subset.pop()

        # Exclude nums[i]
        self.findSubsets(i + 1, nums, subset, subsets)

    def subsets(self, nums: List[int]) -> List[List[int]]:
        subset = []
        subsets = []
        self.findSubsets(0, nums, subset, subsets)
        return subsets

Javascript Code

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    const subsets = [];
    const subset = [];

    function findSubsets(i) {
        if (i === nums.length) {
            subsets.push([...subset]);
            return;
        }

        // Include nums[i]
        subset.push(nums[i]);
        findSubsets(i + 1);

        // Backtrack
        subset.pop();

        // Exclude nums[i]
        findSubsets(i + 1);
    }

    findSubsets(0);

    return subsets;
};

Time & Space Complexity

Time Complexity: O(N × 2^N)

• There are 2^N subsets.
• Copying each subset into the answer takes O(N) time.

Space Complexity:

• O(N) auxiliary space (recursion stack + current subset).
• O(N × 2^N) if the output array is included.

A common mistake is saying the time complexity is just O(2^N). That would be true only if we weren't copying each subset into the result. The copy operation adds the extra N factor.