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 core idea is to use backtracking to explore all possible combinations. We'll iteratively build subsets by considering each element: either include it in the current subset or exclude it.

1. Initialization: Start with an empty subset [].
2. Iteration: Iterate through the input array nums.
3. Choice: For each element num, we have two choices:
   • Include: Add num to the current subset.
   • Exclude: Don't add num to the current subset.
4. Recursion: Recursively explore both choices.
5. Termination: When we reach the end of the nums array, we've explored all possibilities, and the current subset is added to the result.

Explanation

The backtracking approach systematically explores the entire solution space. For each element, we make a choice (include or exclude) and recursively explore the consequences of that choice. The recursive calls build up the subsets gradually. Once we've processed all elements, we have a complete set of all possible subsets.

Code

function subsets(nums: number[]): number[][] {
    const result: number[][] = [];
    const subset: number[] = [];

    function backtrack(index: number): void {
        // Base case: when we've processed all elements, add the current subset to the result
        if (index === nums.length) {
            result.push([...subset]); // Create a copy to avoid modification
            return;
        }

        // Include the current element
        subset.push(nums[index]);
        backtrack(index + 1);

        // Exclude the current element
        subset.pop();
        backtrack(index + 1);
    }

    backtrack(0);
    return 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 perform O(N) operations (copying the subset into the result).
• Space Complexity: O(N), due to the recursive call stack depth (in the worst case, the depth is N) and the space used by the subset array. The space used by the result array is O(N * 2^N) but it is not counted in space complexity analysis for backtracking algorithms as we are not considering the output space in most backtracking algorithms.