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 asks for all possible subsets of a given array. This is a classic combinatorics problem where the power set is generated. We can solve it efficiently using a backtracking approach.

  1. Initialization: Start with an empty subset ([]).

  2. Iteration: Iterate through each element in the input array nums.

  3. Backtracking: For each element, we have two choices:

    • Include: Add the element to the current subset. Recursively explore subsets with this element included.
    • Exclude: Do not add the element to the current subset. Recursively explore subsets with this element excluded.

  4. Base Case: When we reach the end of the nums array, we have a complete subset. Add this subset to the result list.

  5. Result: Return the list of all generated subsets.

Explanation

The backtracking algorithm explores all possible combinations systematically. At each element, it branches into two possibilities: including or excluding the element. This branching ensures that all possible subsets are generated. The recursion unwinds, building up all subsets one element at a time.

Code

def subsets(nums):
    """
    Generates all subsets of a given array using backtracking.

    Args:
      nums: A list of integers.

    Returns:
      A list of lists, where each inner list represents a subset.
    """
    result = []

    def backtrack(index, subset):
        # Base case: reached the end of the array
        if index == len(nums):
            result.append(subset.copy())  # Add a copy to avoid modification
            return

        # Include the current element
        subset.append(nums[index])
        backtrack(index + 1, subset)

        # Exclude the current element
        subset.pop()
        backtrack(index + 1, subset)

    backtrack(0, [])  # Start backtracking from index 0 with an empty subset
    return result

Complexity

  • Time Complexity: O(N * 2N), where N is the length of the input array nums. This is because there are 2N possible subsets, and for each subset, we need to copy it (or create it), which takes O(N) time in the worst case.

  • Space Complexity: O(N * 2N) in the worst case due to the storage of all generated subsets in the result list. The recursive call stack also contributes to space complexity, but it is bounded by O(N) as the depth of recursion is at most N.