64. Subsets · DSA Practice

nums has distinct integers. Return all possible subsets (the power set), without duplicates, in any order.

Example 1

Input: nums = [1,2,3]

Output: [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

Example 2

Input: nums = [0]

Output: [[],[0]]

Hint 1

Each element is either in or out: 2ⁿ subsets.

Hint 2

Backtracking template: choose, explore, un-choose.

BacktrackingBit Manipulation

Approach 1: Bitmask

Numbers 0..2ⁿ−1 encode which elements are taken.

⏱ Time O(n · 2ⁿ)💾 Space O(n · 2ⁿ)

Approach 2: Backtracking ✅

Add the current path at every node of the recursion tree.

⏱ Time O(n · 2ⁿ)💾 Space O(n) + output

Reference solution for Backtracking (time O(n · 2ⁿ), space O(n) + output). Each solution passes every test in all four languages.

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res, path = [], []
        def backtrack(start):
            res.append(path[:])               # every node of the recursion tree is a subset
            for i in range(start, len(nums)):
                path.append(nums[i])          # choose
                backtrack(i + 1)              # explore
                path.pop()                    # un-choose
        backtrack(0)
        return res

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

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

function subsets(nums) {
  const res = [], path = [];
  const backtrack = start => {
    res.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      backtrack(i + 1);
      path.pop();
    }
  };
  backtrack(0);
  return res;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Watch the core idea of this problem step by step. Change the input and press Visualize.

Explained in the lesson Recursion & Backtracking.