D
DevExCode

LeetCode 78: Subsets Solution

Master LeetCode problem 78 (Subsets), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation

To generate all possible subsets of a given set, we can use a backtracking approach. We start with an empty subset and gradually add elements to it, considering each element in the input array. At each step, we either include the current element in the subset or skip it. This process generates all possible combinations of elements.

Algorithm:

  1. Initialize an empty list result to store all subsets.
  2. Define a helper function generateSubsets that takes parameters: the current index in the input array, the current subset being constructed, and the input array nums.
  3. In the helper function:
    • Add the current subset to the result.
    • Iterate over the elements in nums starting from the index provided:
      • Add the current element to the subset.
      • Recursively call the helper function with the next index and the updated subset.
      • Remove the last element from the subset to backtrack and explore other possibilities.
  4. Call the helper function with initial parameters: index = 0, current subset = empty list, and nums.
  5. Return the result containing all subsets.

Time Complexity:

The time complexity of this approach is O(2^N) where N is the number of elements in the input array. This is because for each element, there are two choices - either include it in the subset or skip it.

Space Complexity:

The space complexity is O(N * 2^N) to store all subsets, where N is the number of elements in the input array.

Solution Code

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        generateSubsets(0, new ArrayList<>(), nums, result);
        return result;
    }
    
    private void generateSubsets(int index, List<Integer> current, int[] nums, List<List<Integer>> result) {
        result.add(new ArrayList<>(current));
        
        for (int i = index; i < nums.length; i++) {
            current.add(nums[i]);
            generateSubsets(i + 1, current, nums, result);
            current.remove(current.size() - 1);
        }
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 78 (Subsets)?

This page provides optimized solutions for LeetCode problem 78 (Subsets) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 78 (Subsets)?

The time complexity for LeetCode 78 (Subsets) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 78 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 78 in Java, C++, or Python.

Back to LeetCode Solutions