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.

I really thankful to find this internet site on bing, just what I was looking for : D too bookmarked.

LikeLike