Find All Subsets
You are given an array ‘arr’ of ‘N’ distinct integers. Your task is to find all the non-empty subsets of the array.

Note: You can return the subsets in any order, you don’t have to specifically sort them.

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows The first line of each test case contains a single integers ‘N’ denoting the length of the array. The second line of each test case contains ‘N’ integers denoting the array elements.

Output Format :

For each test case print each subset in a separate line. Output for each test case will be printed in a separate line.

Note :

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints :

1

Question

Find All Subsets

You are given an array ‘arr’ of ‘N’ distinct integers. Your task is to find all the non-empty subsets of the array.

Note: You can return the subsets in any order, you don’t have to specifically sort them.

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows

The first line of each test case contains a single integers ‘N’ denoting the length of the array.

The second line of each test case contains ‘N’ integers denoting the array elements.

Output Format :

For each test case print each subset in a separate line.

Output for each test case will be printed in a separate line.

Note :

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 10      
1 <= N <= 10
10^-9 <= arr[i] <= 10^9

Time limit: 1 sec

Accepted Answer

Power Set Using Bit-Masking

One of the standard and useful method of finding the power set is through bit-masking.

Consider a number with N-bits in its binary representation, if we consider that the state of i^th bit depicts whether the i^tharray element is included in the current subset or not, then we can uniquely identify one of the subsets (as each number has a different binary representation).

Now we can simply iterate from 1 to 2ⁿ-1, each number in this iteration will define a subset uniquely. To generate the subset just check for the bits that are ON in binary representation on the number, and for each ON bit, we will simply include an array element corresponding to its position.

Remember to not include an empty subset in the final answer.

The steps are as follows :

Declare a 2-D container ans to store all the subsets
Run a for loop for num from 1 to 2^N -1
Run inner for loop for i from 0 to N-1
If the i^thbit in num has value equal to 1 then include i^th element of the array in the current subset.
Push each subset generated into ans
Finally, return ans

Space Complexity: OtherExplanation:

O( N * 2^N ), where N is the size of the input array.

Since a total of 2^N-1 subsets are generated, and maximum possible length of each subset is of order N . Hence the space complexity is O(N * 2^N).

Time Complexity: OtherExplanation:

O( N * 2^N ), where N is the size of the input array.

We iterate through N bits for each of the 2^N-1 numbers. Hence the time complexity is O(N * 2^N)

Java (SE 1.8)

/*

    Time Complexity: O(N*2^N)

    Space Complexity: O(N*2^N)



    where N is the size of given input array.

*/



import java.util.ArrayList;



public class Solution {



    static ArrayList> FindAllSubsets(int n, ArrayList arr) {

        // 2D vector to store answer

        ArrayList> ans = new ArrayList<>();



        // Temporary vector to store current subset



        // Iterating over 1 to 2^N-1

        for (int num = 1; num <= Math.pow(2, n) - 1; num++) {



            ArrayList temp = new ArrayList<>();



            // Checking ith bit value of num

            for (int i = 0; i <= n - 1; i++) {



                // If ith bit is ON, adding arr[i] to temporary subset

                if ((num & (1 << i)) == (1 << i)) {

                    temp.add(arr.get(i));

                }



            }



            // Adding the temporary subset to answer

            ans.add(temp);



        }



        // Returning the final answer

        return ans;



    }



}

Python (3.5)

'''
    Time Complexity: O(N*2^N)
    Space Complexity: O(N*2^N)

    where N is the size of given input array.
'''

def FindAllSubsets(n, arr):
    
    # 2D vector to store answer.
    ans = []
    
    # Temporary vector to store current subset.
    # Iterating over 1 to 2^N-1.
    
    for num in range(1, pow(2, n)):
        
        temp = []
        
        # Checking ith bit value of num.
        for i in range(n):
            
            # If ith bit is ON, adding arr[i] to temporary subset.
            if ((num & (1 << i)) == (1 << i)):
                temp.append(arr[i])
                
        # Adding the temporary subset to answer.
        ans.append(temp)
        
    return ans

C++ (g++ 5.4)

/*

    Time Complexity: O(N*2^N)

    Space Complexity: O(N*2^N)



    where N is the size of given input array.

*/



vector> FindAllSubsets(int n, vector &arr){

    

    // 2D vector to store answer

    vector> ans;

    

    // Temporary vector to store current subset

    vector temp;

    

    

    // Iterating over 1 to 2^N-1

    for(int num = 1; num <= pow(2,n)-1; num++){

        

        // Checking ith bit value of num

        for (int i = 0; i <= n-1; i++){

            

            // If ith bit is ON, adding arr[i] to temporary subset

            if((num & (1 << i)) == (1 << i)){

                temp.push_back(arr[i]);

            }

            

        }

        

        // Adding the temporary subset to answer 

        ans.push_back(temp);

        

        // Resetting temporary subset

        temp.clear();

    }

    

    // Returning the final answer

    return ans;

}

Accepted Answer

Backtracking

Each element has 2 choices, it can either be included or excluded.

Using backtracking we can create all the possible subsets, we can add the current element to the temporary array and make a recursive call for the next element, when the function call returns we remove the current element from the temporary array and again make a recursive call for the next element (standard backtracking approach).

Each time we reach the end of the array, we will add the temporary array to the answer.

The steps are as follows :

Initialize a 2D vector ans to store all the subsets
Initialize a vector temp to store the current subset
Create a recursive function SubsetFinder which takes the following parameters: idx to store current index, temp vector to store current subset, ans 2D vector to store all subsets, arr vector that is the input vector.
The initial call is made with idx equal to 0, empty temp vector, empty ans 2D vector, given arr input vector
In SubsetFinder we add the idx^th element to temp vector and recursively call SubsetFinder with idx+1
When a function call is returned, we remove the idx^thelement from temp, and again recursively call SubsetFinder with idx+1
If the value of idx is equal to size of the input array, add temp to ans
Finally, return ans

Space Complexity: OtherExplanation:

O( N * 2^N ), where N is the size of the input array.

Since a total of 2^N-1 subsets are generated, and the maximum possible length of each subset is of order N . Hence the space complexity is O(N * 2^N).

Time Complexity: O(2^n)Explanation:

O( 2 ^ N )

Each element of the array has 2 options therefore overall 2^N for N elements, Hence the time complexity is O( 2 ^ N)

Java (SE 1.8)

/*

    Time Complexity: O(2^N)

    Space Complexity: O(N*2^N)



    where N is the size of given input array.

*/



import java.util.ArrayList;



public class Solution {



    static ArrayList> FindAllSubsets(int n, ArrayList arr) {



        // 2D vector to store answer

        ArrayList> ans = new ArrayList<>();



        // Temporary vector to store current subset

        ArrayList temp = new ArrayList<>();



        // Initial call to recursive function

        SubsetFinder(0, temp, ans, arr);



        // Returning the final answer

        return ans;



    }



    private static void SubsetFinder(int i, ArrayList temp, ArrayList> ans,

            ArrayList arr) {



        // Base condition

        if (i == arr.size()) {

            // Adding non-empty current subset generated to answer

            if (temp.size() > 0) {

                ans.add(temp);

            }

            return;

        }



        // Generating subset which has ith array element in it

        ArrayList temp1 = new ArrayList<>(temp);

        temp1.add(arr.get(i));

        SubsetFinder(i + 1, temp1, ans, arr);



        // Generating subset which doesn't has ith array element

        SubsetFinder(i + 1, temp, ans, arr);

    }



}

C++ (g++ 5.4)

/*

    Time Complexity: O(2^N)

    Space Complexity: O(N*2^N)



    where N is the size of given input array.

*/



void SubsetFinder(int i, vector &temp, vector> &ans, vector &arr){

    

    // Base condition

    if(i==arr.size()){

        // Adding non-empty current subset generated to answer

        if(temp.size()>0){

            ans.push_back(temp);

        }

        return;

    }

    

    // Generating subset which has ith array element in it

    temp.push_back(arr[i]);

    SubsetFinder(i+1,temp,ans,arr);

    temp.pop_back();

    

    // Generating subset which doesn't has ith array element

    SubsetFinder(i+1,temp,ans,arr);

}





vector> FindAllSubsets(int n, vector &arr){

    

    // 2D vector to store answer

    vector> ans;

    

    // Temporary vector to store current subset

    vector temp;

    

    // Initial call to recursive function

    SubsetFinder(0,temp,ans,arr);  

    

    // Returning the final answer

    return ans;

}

Python (3.5)

'''
    Time Complexity: O(2^N)
    Space Complexity: O(N*2^N)

    where N is the size of given input array.
'''

def FindAllSubsets(n, arr): 
    
     # Temporary vector to store current subset.            
    temp = []
    
    for k in range(n + 1):
        
        # Initial call to recursive function.
        SubsetFinder(k, temp, arr)
        
    return temp
        
def SubsetFinder(k, temp, arr, i = 0, temp1 = []):
        
        if len(temp1) > 0:
            
            if len(temp1) == k:  
                temp.append(temp1[:])
                return
            
        for i in range(i, len(arr)):
                
            temp1.append(arr[i])
                
            SubsetFinder(k, temp, arr, i + 1, temp1)
                
            temp1.pop()

You are given an array ‘arr’ of ‘N’ distinct integers. Your task is to find all the non-empty subsets of the array.

Note: You can return the subsets in any order, you don’t have to specifically sort them.

Input Format :

Output Format :

Note :

Constraints :

Top OpenText Technologies Full Stack Engineer interview questions & answers

Popular interview questions of Full Stack Engineer