78. Subsets — LeetCode(Python)

I got you!

Problem:

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]]

Constraints:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • All the numbers of nums are unique.

Solution:

Explanation —

A subset array is maintained and we consider two cases at each step.

So, we iterate through the array in a recursive manner, creating a decision tree at each iteration.

The first case is when we add the next number in the array to our subset and the second case is when we don’t.

The subset is modified accordingly and the function is called recursively to go further down in the decision tree.

When we hit the end of a path in the tree, i.e. reach a leaf node, we append a copy of the subset to our result array. A copy is needed because, in Python, this array might get modified in the result array as well even if we modify it outside of it.

Finally, we call this backtracking function and return the result array.

Time and Space Complexity —

Also, we require a linear amount of extra space to store our subset variable in the recursion stack as we iterate through all elements in the array.

Thus, if n is the length of the array nums,

Time Complexity: O(n * 2^n)

Space Complexity: O(n)

As we can see, this algorithm is no better than just sorting the coordinates by distance. So, we improve upon this approach in the next part of the solution.

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store