Subsets: Introduction

Let’s understand the Subsets pattern, its real-world applications, and some problems we can solve with it.

Overview

The subsets pattern is useful in finding the permutations and combinations of elements in a data structure. The input data structure might be a set containing unique elements. It can also be an array, or a list, which may contain duplicate elements. We then make a series of subsets from the elements in this data structure. The specific subsets generated are based on the conditions that the problem provides us.

We use a programming technique, defined below, known as backtracking to generate the required subsets of a given data structure of elements. The method is to build the subsets incrementally, including or excluding each element of the original data structure, depending on the constraints of the problem. This process is continued recursively for the remaining elements until all desired subsets have been generated.

The following illustration shows how subsets are made from a given array:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.