Subsets

MediumArray Backtracking Bit Manipulation Recursion

A pizza shop wants its online menu to list every possible combination of extra toppings, from a plain pizza with none of them to one with all of them. Each topping is identified by a distinct integer code in nums.

Return all subsets of nums (its power set): every possible selection of toppings, including the empty selection and the full set. Each subset must appear exactly once. The subsets can come in any order, and so can the codes inside each subset.

Example 1

Input: nums = [5,-2,9]
Output: [[],[5],[-2],[5,-2],[9],[5,9],[-2,9],[5,-2,9]]

Explanation: Each of the three toppings is either on the pizza or not, which gives 2³ = 8 combinations.

Example 2

Input: nums = [3,8]
Output: [[],[3],[8],[3,8]]

Explanation: A plain pizza, each topping on its own, and both together.

Constraints

nums holds between 1 and 10 topping codes.
The codes are distinct integers from -10 to 10.

Follow-up: What changes if two toppings can share a code (duplicates in nums) and each distinct combination must still appear only once?

💡 Hint 1

Each element is either in a subset or not, so there are exactly 2^n subsets.

💡 Hint 2

Build the answer step by step: start with [[]], and for every number, add a copy of each existing subset with that number appended.

💡 Hint 3

Alternatively, backtrack: at index i decide to include nums[i] or skip it, and record the current path at every step.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Grow the power set one element at a time. The subsets of the first k numbers, plus a copy of each of them with nums[k] appended, are exactly the subsets of the first k + 1 numbers. Start from [[]] and repeat for every number; the list doubles each round, ending with 2^n subsets. Because the input values are distinct, no subset is produced twice.

Time O(n · 2^n)Space O(n · 2^n) for the output

function subsets(nums) {
  const result = [[]];
  for (const x of nums) {
    const size = result.length;
    for (let i = 0; i < size; i++) result.push([...result[i], x]);
  }
  return result;
}

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());
        for (int x : nums) {
            int size = result.size();
            for (int i = 0; i < size; i++) {
                List<Integer> next = new ArrayList<>(result.get(i));
                next.add(x);
                result.add(next);
            }
        }
        return result;
    }
}

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
function subsets(nums) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit