78. Subsets

Medium

Problem Description

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.

Examples

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]]
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def subsets(nums: List[int]) -> List[List[int]]:
    def backtrack(start: int, curr: List[int]):
        result.append(curr[:])
        
        for i in range(start, len(nums)):
            curr.append(nums[i])
            backtrack(i + 1, curr)
            curr.pop()
    
    result = []
    backtrack(0, [])
    return result

Java Solution


class Solution {
    private List> result;
    
    public List> subsets(int[] nums) {
        result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>());
        return result;
    }
    
    private void backtrack(int[] nums, int start, List curr) {
        result.add(new ArrayList<>(curr));
        
        for (int i = start; i < nums.length; i++) {
            curr.add(nums[i]);
            backtrack(nums, i + 1, curr);
            curr.remove(curr.size() - 1);
        }
    }
}

C++ Solution


class Solution {
private:
    vector> result;
    
    void backtrack(vector& nums, int start, vector& curr) {
        result.push_back(curr);
        
        for (int i = start; i < nums.size(); i++) {
            curr.push_back(nums[i]);
            backtrack(nums, i + 1, curr);
            curr.pop_back();
        }
    }
    
public:
    vector> subsets(vector& nums) {
        vector curr;
        backtrack(nums, 0, curr);
        return result;
    }
};

JavaScript Solution


/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    const result = [];
    
    function backtrack(start, curr) {
        result.push([...curr]);
        
        for (let i = start; i < nums.length; i++) {
            curr.push(nums[i]);
            backtrack(i + 1, curr);
            curr.pop();
        }
    }
    
    backtrack(0, []);
    return result;
};

C# Solution


public class Solution {
    private IList> result;
    
    public IList> Subsets(int[] nums) {
        result = new List>();
        Backtrack(nums, 0, new List());
        return result;
    }
    
    private void Backtrack(int[] nums, int start, List curr) {
        result.Add(new List(curr));
        
        for (int i = start; i < nums.Length; i++) {
            curr.Add(nums[i]);
            Backtrack(nums, i + 1, curr);
            curr.RemoveAt(curr.Count - 1);
        }
    }
}

Complexity Analysis

Solution Explanation

This solution uses backtracking to generate all possible subsets:

Key points: