Find All Subsets

Given a set of ingredients, find all possible combinations of ingredients that can be made. Each combination must be unique.

backtrackingcombinationsrecursionsubsetsarrays

Problem Statement

You are given a list of ingredients, represented as strings. Your task is to write a function that returns all possible combinations (subsets) of these ingredients. The order of ingredients within a combination does not matter, and the order of combinations in the output does not matter. The input list will not contain duplicate ingredients.

Example 1

Input: ["apple", "banana", "cherry"]

Output: [[], ["apple"], ["banana"], ["cherry"], ["apple", "banana"], ["apple", "cherry"], ["banana", "cherry"], ["apple", "banana", "cherry"]]

This example shows all possible combinations of the three ingredients, including the empty combination.

Example 2

Input: ["salt", "pepper"]

Output: [[], ["salt"], ["pepper"], ["salt", "pepper"]]

This example shows all possible combinations of the two ingredients, including the empty combination.

Constraints

-The input list will contain only strings.
-The input list will not contain duplicate strings.
-The length of the input list will be between 0 and 10, inclusive.
-Each string in the input list will have a length between 1 and 10, inclusive.

Brute Force Approach

The most straightforward approach is to generate every possible subset. Imagine flipping a coin for each ingredient: heads, include it; tails, exclude it. By iterating through all possible coin flip combinations, we can generate every subset. We can represent each combination as a binary number, where each bit corresponds to an ingredient.

TimeO(n * 2^n)

SpaceO(n * 2^n)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem