King Of Interviews

Subsets: Given an integer array nums of unique elements, 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]]

Constraints:

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

Try this Problem on your own or check similar problems:

Solution:

class Solution {
  public List<List<Integer>> subsets(int[] nums) {
      List<List<Integer>> result = new ArrayList<>();
      helper(0, nums, new ArrayList<>(), result);
      return result;
  }

  private void helper(int index, int[] nums, List<Integer> currentList, List<List<Integer>> result){
      if(index == nums.length){
          result.add(new ArrayList<>(currentList));
          return;
      }

      currentList.add(nums[index]);
      helper(index + 1, nums, currentList, result);
      currentList.remove(currentList.size() - 1);
      helper(index + 1, nums, currentList, result);
  }
}

Time/Space Complexity:

Time Complexity: O(n*2^n)
Space Complexity: O(n)

Explanation:

As with all backtracking problems we first define (check Letter Case Permutation ) our result which will be modified inside the helper function. We call the helper funtion and return back the result. The time complexity of calculating power set (all subsets) is O(2^n). To figure this imagine all binary number from 0 to 7, you will need to have 3 bits to represent all numbers in the range (2^3 = 8), or in other way if you have n = 3 you can represent 2^3=8 numbers, but how does this help us with the subsets? Well let’s give an example x=6 or in binary 110, that number can represent the following statement: The first number in array is present in the subset (because we have 1 at first place), second is also present, but the third isn’t (since last bit is 0). If we list all numbers from 0..7 we will see it will give us all possible configurations based on input array, those configurations actually make our power set. Also note that for time complexity we have n multiplier since we’re also copying the list inside the base case (index == nums.length). For space complexity we only go n levels deep the recursion stack (where n is the length of input array), we do not count space that is used for returning the result.

So, what do we do in the helper function? We have a index to track in each recursion call our position and get corresponding element from input array, if index == nums.length that means we exhausted all options and we can add currentList to the result. Now to the decision making, just as we have 0 or 1 we can decide whether to pick element or not. So for the first branch of recursion tree, we decide to pick the element, and for the second we decide to omit it (notice we have to remove it from the currentList).

Subsets