Identify

• when you need to find the combinations or permutations of a given set

Motive

• a huge number of coding interview problems involve dealing with Permutations and Combinations of a given set of elements
• the pattern Subsets describes an efficient Breadth First Search (BFS) approach to handling all these problems

Steps

• given a set of [1, 5, 3]
  1. start with an empty set: [[]]
  2. add the first number (1) to all the existing subsets to create new subsets: [[], [1]];
  3. add the second number (5) to all the existing subsets: [[], [1], [5], [1,5]];
  4. add the third number (3) to all the existing subsets: [[], [1], [5], [1,5], [3], [1,3], [5,3], [1,5,3]].

Complexity

Time: O(2^n)

• since, in each step, number of subsets doubles.

Space: O(2^n)

Common Problems

• [ ] LeetCode 78 - Subsets [medium]
• [ ] LeetCode 90 - Subsets II [medium]
• [ ] Subsets With Duplicates (easy)
• [ ] String Permutations by changing case (medium)