Finding all Subsets of a given set

Hi Geeks! Welcome to 100 Days Leetcode Challenge.

Day 3

In this article, I’ll explain about how to find all the subsets of a given set(power set).

Here is our given problem,

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

PRoblem explanation

We have to return the subsets in any order we like.

Think about this problem for a minute.

If you do not get any idea of this problem, look at below, how to approach this finding the all subsets of given set.

HOW TO APPROACH THIS PROBLEM?

First thing – How to calculate total number of subsets to print

The first thing you might consider when you think about this problem is how many subsets are there for the given array or set.

So when n = 2, the total number of subsets we have to print is 4, when n = 3, the total number of subsets we have to print is 8(2 to the power of 3), when n = 4, the total number of subsets we have to print is 16(2 to the power of 4).

Solution

We going to solve this problem with backtracking approach. This approach helps to solve more problems like permutations, combinations in this way.

You are going to see the power of recursion here.

    class Solution {
      public List<List<Integer>> subsets(int[] nums) {
        
        //List of lists
        List<List<Integer>> list = new ArrayList<>();
        
        //temporary list to process
        List<Integer> tempList = new ArrayList<>();
        
        //to track the positions, simple dummy variable
        int start = 0;
        
        backtrack(list, tempList, nums, start);
        
        return list;
    }
    
    private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){
        
    list.add(new ArrayList<>(tempList));
        
    for(int i = start; i < nums.length; i++){
        
        tempList.add(nums[i]);
        
        backtrack(list, tempList, nums, i + 1);
        
        tempList.remove(tempList.size() - 1);
    }
    }
}

Don’t worry, if you didn’t understand this solution, I make it clear with great examples how it works.

How Backtracking works here?

Just for understanding, I’m giving line numbers to these below code.

Before function call, what we have now,

        //List of lists
        List<List<Integer>> list = new ArrayList<>();
        
        //temporary list to process
        List<Integer> tempList = new ArrayList<>();
        
        //to track the positions, simple dummy variable
        int start = 0;
        
        backtrack(list, tempList, nums, start);

This above code finally calls the backtrack() method. Let’s see, how this backtrack() method works.

Here, the number 1 to 5 denotes the line number of the code. I used this way, to explain how backtracking works for the input array of {1, 2}.

When first call happens, line be line, I captured whatever happens in the code.

Similarly for other calls also.

I ask you to observe these diagram very deeply to understand the solution.

Compare line number code with these diagrams, to get better understanding.

That’s all about finding all subsets of set(power set). I hope you understood the problem and solution well.


If you like this article, please follow my blog by entering your email id, to get notifications of Data structures and Algorithms Problems with clear infographic explanations at your inbox.

Processing…
Success!

One thought on “Finding all Subsets of a given set

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