Find all Subsets

Problem Link

Subsets – LeetCode

Problem: Subsets

Problem Statement

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. You may return the subsets in any order.

Examples

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

Constraints

• 1 <= nums.length <= 10

• -10 <= nums[i] <= 10

• All elements in nums are unique.

Intuition

This is a subset generation problem. For each element, we have two choices:

• Include the current element in the current subset.

• Exclude it and move to the next.

This is a perfect scenario for applying the Input-Output or Include-Exclude recursion pattern.

Include-Exclude (Input-Output) Method Explanation

Function Signature

void helper(int idx, List<Integer> output, List<List<Integer>> ans, int[] nums)

Base Case

If idx == nums.length, we have considered all elements:

• Add the current output subset to ans.

Induction

At every index idx, we make two choices:

1. Include nums[idx] → add to output, recurse for next index.

2. Exclude nums[idx] → do not add to output, recurse for next index.

Backtracking

When including, we must remove the last added element after the recursive call to reset state for exclusion.

Code (Java)

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

    private void helper(int idx, List<Integer> output, List<List<Integer>> ans, int[] nums) {
        // Base Case
        if (idx == nums.length) {
            ans.add(new ArrayList<>(output));
            return;
        }

        // Include current element
        output.add(nums[idx]);
        helper(idx + 1, output, ans, nums);

        // Backtrack and exclude
        output.remove(output.size() - 1);
        helper(idx + 1, output, ans, nums);
    }
}

Time and Space Complexity

• Time Complexity: O(2^n)

  • Each element has two choices → total 2^n subsets.

• Space Complexity:

  • O(n) recursion stack

  • O(2^n * n) to store all subsets

Dry Run

Input: nums = [1, 2]

Call Tree:

                []
             /      \
          [1]        []
         /   \      /   \
     [1,2]  [1]   [2]   []

Output:
[[], [2], [1], [1,2]] (order may vary)

Conclusion

The Include-Exclude (Input-Output) recursion is a fundamental technique for solving subset, permutation, and combination problems. It clearly demonstrates the decision tree of choosing or skipping elements and helps build recursive problem-solving skills.