algoadvance

Leetcode 78. Subsets

Problem Statement

Given an integer array nums of unique elements, return all possible subsets (the power set). The solution should not contain duplicate subsets, and the order of the subsets does not matter.

Clarifying Questions

1. Input Constraints:
   • What is the range of the elements in nums?
   • What is the maximum length of nums?
2. Output Format:
   • Should the subsets be sorted in any particular order?
   • Should the individual elements in each subset be sorted?

Typical assumptions:

• The size of nums can vary, but let’s say up to 10-15 elements for practical purposes.
• The elements are unique, as stated.
• The output can be in any order, and the internal elements of each subset do not need to be sorted, as long as the subsets are correct.

Strategy

To solve this problem, we’ll use backtracking:

1. Backtracking Approach:
   • Use recursion to explore all possible subsets.
   • At each recursion level, consider two choices: either include the current element or exclude it.
2. Iterative Approach:
   • Start with an empty subset.
   • For each element in the array, add it to existing subsets to form new subsets.

We’ll utilize the backtracking approach here, which allows us to naturally handle the recursive nature of subset generation.

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<>();
        generateSubsets(0, nums, new ArrayList<>(), result);
        return result;
    }

    private void generateSubsets(int index, int[] nums, List<Integer> current, List<List<Integer>> result) {
        // Add the current subset to the result list
        result.add(new ArrayList<>(current));
        
        // Iterate from the current index to the end of the nums array
        for (int i = index; i < nums.length; i++) {
            // Include nums[i] in the current subset
            current.add(nums[i]);
            
            // Recur to the next element
            generateSubsets(i + 1, nums, current, result);
            
            // Exclude the last element from the current subset to backtrack
            current.remove(current.size() - 1);
        }
    }

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

Time Complexity

The time complexity of the backtracking approach is (O(2^n \cdot n)):

• 2^n represents the total number of subsets (each element has two choices: include or exclude).
• n is the time to copy the current subset to the result.

The space complexity is also (O(2^n \cdot n)) due to the space required to store all subsets, each of which can be of size (n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?