Trusted answers to developer questions

Gopi Gorantala

In this coding problem, we need to find the power-set of given input without duplicates.

In this article, we discuss the subsets of a given input. This is one of the most popular questions asked in coding interviews.

Companies that have asked this in their coding interview are Apple, Microsoft, Amazon, Facebook, and many more.

We need to write a program that finds all possible subsets (the power set) of a given input. The solution set must not contain duplicate subsets.

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

Input: [100] Output: [[], [100]]

- The subsets of any given input are equal to its power set.
- If input
`n = 3`

, then powerset =>`2^n`

=`2^3`

=`8`

. - Assume input has a length greater than or equal to
`1`

.

Hint: Use the left-shift operator to achieve this.

In this program, we find the power set of a given input using bitwise operations. In general, if we have `n`

elements then the subsets are `2^n`

subsets. So for every possible case of having at least two elements, we can see that an element is present and not present in the subsets. Think of a solution that is iterative, uses bitwise operators, and generates the powerset.

Here is how we generate each subset using the outer-loop variable `counter`

. Here is a table indicating how the value gets generated based on the `counter`

input.

Counter (in decimal) | Counter (in binary) | Subset |

0 | 000 | [] |

1 | 001 | [1] |

2 | 010 | [2] |

3 | 011 | [1, 2] |

4 | 100 | [3] |

5 | 101 | [1, 3] |

6 | 110 | [2, 3] |

7 | 111 | [1, 2, 3] |

We need to consider a `counter`

variable that starts from `0`

to `2^n - 1`

.

For every value, we are considering the binary representation and here we use the set bits in the binary representation to generate corresponding subsets.

- If all set bits are
`0`

, then the corresponding subset is empty`[]`

. - If the last bit is
`1`

, then we put`1`

in the subset as`[1]`

.

We use two loops here, the outer-loop starts from `0`

to `2^n - 1`

, and the inner loop continues to input array length `n`

.

In the inner loop, we conditionally check `(counter & (1 << j)) != 0)`

, if yes, then we print the corresponding element from an array.

import java.util.ArrayList; import java.util.List; class Subsets { public static void main(String[] args) { int[] input = {1, 2, 3}; System.out.println(subsets(input)); } public static List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<>(); int n = nums.length; int powSize = (int) Math.pow(2, n); for (int i = 0; i < powSize; i++) { List<Integer> val = new ArrayList<>(); for (int j = 0; j < n; j++) { if ((i & (1 << j)) != 0) { val.add(nums[j]); } } result.add(val); } return result; } }

Solution

**Time Complexity:** `O(n*2^n)`

the time complexity is `n`

times the power set.

**Space Complexity:** `O(2^n)`

we are storing `2^n`

subset elements in an array. So the extra space is directly proportional to `O(2^n)`

.

Check out this course on how to solve problems using bit manipulation: Master Bit Manipulation for Coding Interviews.

RELATED TAGS

java

CONTRIBUTOR

Gopi Gorantala

RELATED COURSES

View all Courses

Keep Exploring

Related Courses