Power set

Bit Manipulation (9 Part Series)

1 Minimum Bit Flips to Convert Number
2 Bit Manipulation tips and tricks
… 5 more parts…
3 Power set
4 Single Number I
5 Single Number 2
6 Single number 3
7 Xor of N numbers
8 Divide two integers without using division or multiplication operators
9 Minimize XOR

Problem

Backtracking approach:
TC:(2^n) i.e. exponential time complexity (Since we are left with two choice at every recursive call i.e. either to consider the value at ‘index’ or not that leads to 2 possible outcome, this will happen for n times)
SC:(2^n)*(n), n for temp ArrayList<>() and 2^n for the main ArrayList<>();

<span>class</span> <span>Solution</span> <span>{</span>
    <span>public</span> <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>subsets</span><span>(</span><span>int</span><span>[]</span> <span>nums</span><span>)</span> <span>{</span>
        <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>list</span> <span>=</span> <span>new</span> <span>ArrayList</span><span><>();</span>
        <span>powerSet</span><span>(</span><span>nums</span><span>,</span><span>0</span><span>,</span><span>list</span><span>,</span><span>new</span> <span>ArrayList</span><span><</span><span>Integer</span><span>>());</span>
        <span>return</span> <span>list</span><span>;</span>
    <span>}</span>
    <span>public</span> <span>void</span> <span>powerSet</span><span>(</span><span>int</span> <span>[]</span> <span>nums</span><span>,</span> <span>int</span> <span>index</span> <span>,</span> <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>list</span><span>,</span> <span>List</span><span><</span><span>Integer</span><span>></span> <span>l</span><span>){</span>
        <span>//base case</span>
        <span>if</span><span>(</span><span>index</span> <span>==</span><span>nums</span><span>.</span><span>length</span><span>){</span>
            <span>list</span><span>.</span><span>add</span><span>(</span><span>new</span> <span>ArrayList</span><span><>(</span><span>l</span><span>));</span>
            <span>return</span><span>;</span>
        <span>}</span>
        <span>//take</span>
        <span>l</span><span>.</span><span>add</span><span>(</span><span>nums</span><span>[</span><span>index</span><span>]);</span> <span>//consider the value at 'index'</span>
        <span>powerSet</span><span>(</span><span>nums</span><span>,</span><span>index</span><span>+</span><span>1</span><span>,</span><span>list</span><span>,</span><span>l</span><span>);</span>
        <span>//dont take;</span>
        <span>l</span><span>.</span><span>remove</span><span>(</span><span>l</span><span>.</span><span>size</span><span>()-</span><span>1</span><span>);</span><span>// don't consider the value at 'index'</span>
        <span>powerSet</span><span>(</span><span>nums</span><span>,</span><span>index</span><span>+</span><span>1</span><span>,</span><span>list</span><span>,</span><span>l</span><span>);</span>
    <span>}</span>
<span>}</span>
<span>class</span> <span>Solution</span> <span>{</span>
    <span>public</span> <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>subsets</span><span>(</span><span>int</span><span>[]</span> <span>nums</span><span>)</span> <span>{</span>
        <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>list</span> <span>=</span> <span>new</span> <span>ArrayList</span><span><>();</span>
        <span>powerSet</span><span>(</span><span>nums</span><span>,</span><span>0</span><span>,</span><span>list</span><span>,</span><span>new</span> <span>ArrayList</span><span><</span><span>Integer</span><span>>());</span>
        <span>return</span> <span>list</span><span>;</span>
    <span>}</span>
    <span>public</span> <span>void</span> <span>powerSet</span><span>(</span><span>int</span> <span>[]</span> <span>nums</span><span>,</span> <span>int</span> <span>index</span> <span>,</span> <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>list</span><span>,</span> <span>List</span><span><</span><span>Integer</span><span>></span> <span>l</span><span>){</span>
        <span>//base case</span>
        <span>if</span><span>(</span><span>index</span> <span>==</span><span>nums</span><span>.</span><span>length</span><span>){</span>
            <span>list</span><span>.</span><span>add</span><span>(</span><span>new</span> <span>ArrayList</span><span><>(</span><span>l</span><span>));</span>
            <span>return</span><span>;</span>
        <span>}</span>
        <span>//take</span>
        <span>l</span><span>.</span><span>add</span><span>(</span><span>nums</span><span>[</span><span>index</span><span>]);</span> <span>//consider the value at 'index'</span>
        <span>powerSet</span><span>(</span><span>nums</span><span>,</span><span>index</span><span>+</span><span>1</span><span>,</span><span>list</span><span>,</span><span>l</span><span>);</span>
        <span>//dont take;</span>
        <span>l</span><span>.</span><span>remove</span><span>(</span><span>l</span><span>.</span><span>size</span><span>()-</span><span>1</span><span>);</span><span>// don't consider the value at 'index'</span>
        <span>powerSet</span><span>(</span><span>nums</span><span>,</span><span>index</span><span>+</span><span>1</span><span>,</span><span>list</span><span>,</span><span>l</span><span>);</span>
    <span>}</span>
<span>}</span>
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        powerSet(nums,0,list,new ArrayList<Integer>());
        return list;
    }
    public void powerSet(int [] nums, int index , List<List<Integer>> list, List<Integer> l){
        //base case
        if(index ==nums.length){
            list.add(new ArrayList<>(l));
            return;
        }
        //take
        l.add(nums[index]); //consider the value at 'index'
        powerSet(nums,index+1,list,l);
        //dont take;
        l.remove(l.size()-1);// don't consider the value at 'index'
        powerSet(nums,index+1,list,l);
    }
}

Enter fullscreen mode Exit fullscreen mode

Using Bit Manipulation:
TC: O(2^n)*n
SC: O(2^n)*n, (2^n for the main list, and n for the subset lists, well not all the subsets will be of size n but still we can assume that is the case)

pre-requisite: check if ith bit is set or not ( refer the Bit manipulation tips and tricks page for more details)
Intuition:
If all the no . subsets are represented as binary values,
for example : if n = 3 i.e. array having 3 value in it.
there will be 2^n = 8 subsets
8 subsets can also be represented as

We will take into consideration that if bit value is 1 then that index value in the nums[] should be taken into consideration for forming the subset.
This way we will be able to create all the subsets

<span>class</span> <span>Solution</span> <span>{</span>
    <span>public</span> <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>subsets</span><span>(</span><span>int</span><span>[]</span> <span>nums</span><span>)</span> <span>{</span>
        <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>list</span> <span>=</span> <span>new</span> <span>ArrayList</span><span><>();</span>
        <span>int</span> <span>n</span> <span>=</span> <span>nums</span><span>.</span><span>length</span><span>;</span>
        <span>int</span> <span>noOfSubset</span> <span>=</span> <span>1</span><span><<</span><span>n</span><span>;</span> <span>// this is nothing but 2^n, i.e if there are n elements in the array, they will form 2^n subsets</span>
        <span>for</span><span>(</span><span>int</span> <span>num</span> <span>=</span> <span>0</span><span>;</span><span>num</span><span><</span><span>noOfSubset</span><span>;</span><span>num</span><span>++){</span> <span>/// all possible subsets numbers</span>
            <span>List</span><span><</span><span>Integer</span><span>></span> <span>l</span> <span>=</span> <span>new</span> <span>ArrayList</span><span><>();</span>
            <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span><span>0</span><span>;</span><span>i</span><span><</span><span>n</span><span>;</span><span>i</span><span>++){</span><span>// for the given subset number find which index value to pick </span>
                <span>if</span><span>((</span><span>num</span> <span>&</span> <span>(</span><span>1</span><span><<</span><span>i</span><span>))!=</span><span>0</span><span>)</span> <span>l</span><span>.</span><span>add</span><span>(</span><span>nums</span><span>[</span><span>i</span><span>]);</span> 
            <span>}</span>
            <span>list</span><span>.</span><span>add</span><span>(</span><span>l</span><span>);</span>
        <span>}</span>
        <span>return</span> <span>list</span><span>;</span>
    <span>}</span>
<span>}</span>
<span>class</span> <span>Solution</span> <span>{</span>
    <span>public</span> <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>subsets</span><span>(</span><span>int</span><span>[]</span> <span>nums</span><span>)</span> <span>{</span>
        <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>list</span> <span>=</span> <span>new</span> <span>ArrayList</span><span><>();</span>
        <span>int</span> <span>n</span> <span>=</span> <span>nums</span><span>.</span><span>length</span><span>;</span>
        <span>int</span> <span>noOfSubset</span> <span>=</span> <span>1</span><span><<</span><span>n</span><span>;</span> <span>// this is nothing but 2^n, i.e if there are n elements in the array, they will form 2^n subsets</span>

        <span>for</span><span>(</span><span>int</span> <span>num</span> <span>=</span> <span>0</span><span>;</span><span>num</span><span><</span><span>noOfSubset</span><span>;</span><span>num</span><span>++){</span> <span>/// all possible subsets numbers</span>
            <span>List</span><span><</span><span>Integer</span><span>></span> <span>l</span> <span>=</span> <span>new</span> <span>ArrayList</span><span><>();</span>
            <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span><span>0</span><span>;</span><span>i</span><span><</span><span>n</span><span>;</span><span>i</span><span>++){</span><span>// for the given subset number find which index value to pick </span>
                <span>if</span><span>((</span><span>num</span> <span>&</span> <span>(</span><span>1</span><span><<</span><span>i</span><span>))!=</span><span>0</span><span>)</span> <span>l</span><span>.</span><span>add</span><span>(</span><span>nums</span><span>[</span><span>i</span><span>]);</span> 
            <span>}</span>
            <span>list</span><span>.</span><span>add</span><span>(</span><span>l</span><span>);</span>
        <span>}</span>
        <span>return</span> <span>list</span><span>;</span>
    <span>}</span>
<span>}</span>

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        int n = nums.length;
        int noOfSubset = 1<<n; // this is nothing but 2^n, i.e if there are n elements in the array, they will form 2^n subsets

        for(int num = 0;num<noOfSubset;num++){ /// all possible subsets numbers
            List<Integer> l = new ArrayList<>();
            for(int i =0;i<n;i++){// for the given subset number find which index value to pick 
                if((num & (1<<i))!=0) l.add(nums[i]); 
            }
            list.add(l);
        }
        return list;
    }
}

Enter fullscreen mode Exit fullscreen mode

Bit Manipulation (9 Part Series)

1 Minimum Bit Flips to Convert Number
2 Bit Manipulation tips and tricks
… 5 more parts…
3 Power set
4 Single Number I
5 Single Number 2
6 Single number 3
7 Xor of N numbers
8 Divide two integers without using division or multiplication operators
9 Minimize XOR

原文链接：Power set