Gnerate all possible subsets – Subsets

Medium

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.

Implementation

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

Complexity Analysis

  • Time Complexity: O(N × 2N). 2N to generate all subsets and then O(N) to copy each set into output list.
  • Space Complexity: O(N × 2N)  to keep all the subsets of length  N, since each of N elements could be present or absent.

Categories: Backtracking

Tagged as: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s