Subsets

Problem

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]]

Constraints:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • All the numbers of nums are unique.

Solution

Time: 2^n

Space: n

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        var ans = new ArrayList<List<Integer>>();
        solve(nums, 0, List.of(), ans);
        return ans;
    }

    public void solve(int[] nums, int n, List<Integer> curr, List<List<Integer>> ans) {
        if (n == nums.length) {
            ans.add(curr);
            return;
        }
        // we have the choice of adding or not

        // don't add
        solve(nums, n + 1, curr, ans);

        // add
        var copy = new ArrayList<>(curr);
        copy.add(nums[n]);
        solve(nums, n + 1, copy, ans);
    }
}

Recent posts from blogs that I like

British Impressionists on the beach 2

Paintings by Philip Wilson Steer, Blanche back in Dieppe, Walter Sickert, the Bavarian son of a Danish artist and his British wife, and the Irish artist John Lavery, and more.

via The Eclectic Light Company

You learn more about writing from close reading than from writing advice

+ how David Foster Wallace creates drive in an essay

via Henrik Karlsson

How to find meaning in large tech companies

Why do many people hate working in large tech companies?

The obvious answer is “because organizational dysfunction stops them from doing the things they want to do”. Engineers like to write code and ship things, and if their company’s dysfunction is preventing that, it’ll make them unhappy. Right?

S...

via Sean Goedecke