Subsets medium

Problem Statement

Given an integer array nums, 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]]

Steps

The problem of generating all subsets of a set is a classic combinatorial problem. We can solve this using a backtracking approach. The core idea is to explore all possible combinations by iteratively deciding whether to include each element in the current subset or not.

1. Initialization: Start with an empty subset ([]).
2. Iteration: Iterate through each element in the input array nums.
3. Choice: For each element, we have two choices:
   • Include the element in the current subset.
   • Exclude the element from the current subset.
4. Backtracking: Explore both choices recursively. When we reach the end of the nums array, we've formed a complete subset, so add it to the result. Then, backtrack (remove the last added element) to explore the other branches of the decision tree.
5. Result: The final result will contain all possible subsets.

Explanation

The backtracking approach systematically explores all possible combinations. Imagine a binary tree where each level represents a decision (include or exclude an element). Each path from the root to a leaf node represents a unique subset. The backtracking ensures we explore all paths.

For example, with nums = [1, 2, 3]:

• Start with []
• Consider 1:
  • Include 1: [1] -> Consider 2:
    • Include 2: [1, 2] -> Consider 3:
      • Include 3: [1, 2, 3] (add to result)
      • Exclude 3: [1, 2] (add to result)
    • Exclude 2: [1] -> Consider 3:
      • Include 3: [1, 3] (add to result)
      • Exclude 3: [1] (add to result)
  • Exclude 1: [] -> Consider 2: ...and so on.

Code

import java.util.ArrayList;
import java.util.List;

public class Subsets {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), nums, 0);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> currentSubset, int[] nums, int index) {
        // Base case: We've reached the end of the nums array, add the current subset to the result
        if (index == nums.length) {
            result.add(new ArrayList<>(currentSubset)); // Create a copy to avoid modification
            return;
        }

        // Include the current element
        currentSubset.add(nums[index]);
        backtrack(result, currentSubset, nums, index + 1);

        // Exclude the current element
        currentSubset.remove(currentSubset.size() - 1);
        backtrack(result, currentSubset, nums, index + 1);
    }

    public static void main(String[] args) {
        Subsets subsets = new Subsets();
        int[] nums = {1, 2, 3};
        List<List<Integer>> result = subsets.subsets(nums);
        System.out.println(result);
    }
}

Complexity

• Time Complexity: O(N * 2^N), where N is the length of the input array. This is because there are 2^N possible subsets, and for each subset, we might need to perform O(N) operations (e.g., copying the subset).
• Space Complexity: O(N * 2^N) to store all the subsets in the result list. The recursion depth is also O(N) in the worst case.