65. Subsets

MediumArray Backtracking Bit Manipulation Recursion

Given an array nums of distinct integers, return every possible subset of it (its power set), including the empty subset and nums itself.

Each subset must appear exactly once. The subsets may be returned in any order, and the numbers inside a subset may be in any order too.

Example 1

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

Explanation: Three elements give 2³ = 8 subsets.

Example 2

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

Example 3

Input: nums = [4,-2]
Output: [[],[4],[-2],[4,-2]]

Constraints

1 <= nums.length <= 10
-10 <= nums[i] <= 10
All values in nums are distinct

Follow-up: What changes if nums may contain duplicates and the answer must still list each distinct subset 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