LietCode
Subsets

Subsets

Abhi's photo
Abhi
·

3 min read

Explain the Problem

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

The solution set must not contain duplicate subsets and the subsets can be returned in any order.

Example:

Input: nums = [1, 2, 3]

Output:

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

Short, Easy-to-Remember Solution/Approach

To solve this problem, we can use a recursive backtracking approach:

  1. Recursive Function: We'll create a helper function that builds subsets by including or excluding each element.

  2. Backtracking: If we reach the end of the array, we add the current subset to the result list.

Solution in JavaScript with Code Commenting

Here's the JavaScript solution with detailed comments:

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

  // Helper function for backtracking
  function backtrack(start, path) {
    // Add the current path to the result
    result.push([...path]);

    // Loop through the elements starting from the current index
    for (let i = start; i < nums.length; i++) {
      // Include the current element in the path
      path.push(nums[i]);
      // Recurse with the updated path
      backtrack(i + 1, path);
      // Backtrack: remove the last element from the path
      path.pop();
    }
  }

  // Start the backtracking with an empty path
  backtrack(0, []);

  return result;
}

Explanation of the Solution in Simple Terms

Imagine you have a box of unique toys, and you want to find all the different groups of toys you can form.

  • Recursive Function: This is like a helper that tries different combinations of toys to see all possible groups.

  • Backtracking: This means if the current group doesn't need more toys (either because you've considered all toys or you've tried all possibilities), you go back and try a different combination.

For each toy, you either add it to your current group or skip it and try the next toy. If you reach the end of the list, you save the current group. If not, you undo your last step and try something else.

Code Explanation in Pointers

  1. Initialize Result Array: Create an empty array to store all subsets.

  2. Define Backtracking Function: Create a recursive function to explore different subsets.

  3. Add Current Path: Add the current subset (path) to the result.

  4. Loop Through Elements: Try each element from the current index onwards.

  5. Add to Path: Include the current element in the subset.

  6. Recursive Call: Call the function recursively with the updated subset.

  7. Backtrack: Remove the last element from the subset before trying the next one.

Complexity Analysis

  • Time Complexity: O(N * 2^N), where N is the number of elements in the input array. This is because we generate all subsets.

  • Space Complexity: O(N * 2^N), due to the recursion stack and the result list storing all subsets.

backtracking