mediumBacktracking

Subsets

Generate every subset of distinct integers. Sort values within each subset and order subsets lexicographically, with the empty subset first.

LeetCode ↗

Work through the cases

3 examples

Input notation

Distinct integers separated by spaces; at most 12 values.

Expected result

One subset per line in bracket notation without spaces.

Case 1

Input

1 2

Expected output

[]
[1]
[1,2]
[2]

Case 2

Input

Expected output

[]
[3]

Case 3

Input

-1

Expected output

[]
[-1]

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

A subset is a choose/skip for each element, 2^n of them. n ≤ 10, so listing all is fine. We could rebuild from each mask, or recurse. Recursion is the direct picture: from index i, skip nums[i] then take it and pop. At i=n copy the path into the answer. Distinct elements mean no duplicate subsets.

We design a function dfs(i), which represents starting the search from the ith element of the array for all subsets. The execution logic of the function dfs(i) is as follows:

- If i = n, it means the current search has ended. Add the current subset t to the answer array ans, and then return. - Otherwise, we can choose not to select the current element and directly execute dfs(i + 1); or we can choose the current element, i.e., add the current element nums[i] to the subset t, and then execute dfs(i + 1). Note that we need to remove nums[i] from the subset t after executing dfs(i + 1) (backtracking).

In the main function, we call dfs(0), i.e., start searching all subsets from the first element of the array. Finally, return the answer array ans.

The time complexity is O(n × 2^n), and the space complexity is O(n). Here, n is the length of the array. There are a total of 2^n subsets, and each subset takes O(n) time to construct.

class Solution {
    private List<List<Integer>> ans = new ArrayList<>();
    private List<Integer> t = new ArrayList<>();
    private int[] nums;

    public List<List<Integer>> subsets(int[] nums) {
        this.nums = nums;
        dfs(0);
        return ans;
    }

    private void dfs(int i) {
        if (i == nums.length) {
            ans.add(new ArrayList<>(t));
            return;
        }
        dfs(i + 1);
        t.add(nums[i]);
        dfs(i + 1);
        t.remove(t.size() - 1);
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.