Swift Program to Generate all Subsets of a Set using Recursion

Swift – Generate all Subsets of a Set using Recursion

In this tutorial, we will learn how to generate all subsets (also called the power set) of a set using recursion in Swift. We will understand the concept of subsets, write an algorithm, and implement the solution step by step with a complete Swift program and output.

---

What are Subsets?

A subset is a collection of elements from a set where the order of elements does not matter, and the elements are unique. For example, if the input set is {1, 2}, the subsets are:

• {} (the empty subset)
• {1}
• {2}
• {1, 2}

The total number of subsets of a set containing n elements is 2n, including the empty subset.

---

Algorithm to Generate Subsets Using Recursion

1. Take the input set as an array.
2. Base Case: If the set is empty, return an array containing only the empty subset [[]].
3. Recursive Case:
   1. Exclude the first element and recursively find subsets of the remaining set.
   2. Include the first element in each of these subsets.
   3. Combine both sets of subsets (with and without the first element).

This approach ensures that subsets are generated recursively for all possible combinations.

---

Step-by-Step Implementation in Swift

1. Define the Base Case

Create a recursive function that returns an array containing only the empty subset when the input set is empty:

func generateSubsets(_ set: [Int]) -> [[Int]] {
    if set.isEmpty {
        return [[]] // Base case: Only the empty subset
    }
    return [] // Placeholder for recursive case
}

2. Add the Recursive Case

Implement the logic to generate subsets with and without the first element:

func generateSubsets(_ set: [Int]) -> [[Int]] {
    if set.isEmpty {
        return [[]] // Base case
    }
    
    let first = set[0] // Take the first element
    let rest = Array(set.dropFirst()) // Take the rest of the set
    
    // Recursively generate subsets for the remaining set
    let subsetsWithoutFirst = generateSubsets(rest)
    
    // Generate subsets including the first element
    let subsetsWithFirst = subsetsWithoutFirst.map { subset in
        return [first] + subset
    }
    
    // Combine subsets with and without the first element
    return subsetsWithoutFirst + subsetsWithFirst
}

Explanation:

• if set.isEmpty: Returns [[]] as the only subset for an empty set.
• let first = set[0]: Extracts the first element of the input set.
• Array(set.dropFirst()): Removes the first element to process the rest of the set.
• generateSubsets(rest): Recursively finds subsets of the remaining elements.
• subsetsWithFirst: Adds the first element to each subset of the remaining set.
• subsetsWithoutFirst + subsetsWithFirst: Combines the subsets with and without the first element.

3. Test the Function

Let’s test the function with some example inputs:

// Test cases
let subsets1 = generateSubsets([1, 2])
print("Subsets of [1, 2]: \(subsets1)")

let subsets2 = generateSubsets([1, 2, 3])
print("Subsets of [1, 2, 3]: \(subsets2)")

let subsets3 = generateSubsets([])
print("Subsets of []: \(subsets3)")

---

Complete Swift Program

Here’s the complete Swift program:

import Foundation

// Recursive function to generate all subsets of a set
func generateSubsets(_ set: [Int]) -> [[Int]] {
    if set.isEmpty {
        return [[]] // Base case
    }
    
    let first = set[0] // Take the first element
    let rest = Array(set.dropFirst()) // Take the rest of the set
    
    // Recursively generate subsets for the remaining set
    let subsetsWithoutFirst = generateSubsets(rest)
    
    // Generate subsets including the first element
    let subsetsWithFirst = subsetsWithoutFirst.map { subset in
        return [first] + subset
    }
    
    // Combine subsets with and without the first element
    return subsetsWithoutFirst + subsetsWithFirst
}

// Test cases
let subsets1 = generateSubsets([1, 2])
print("Subsets of [1, 2]: \(subsets1)")

let subsets2 = generateSubsets([1, 2, 3])
print("Subsets of [1, 2, 3]: \(subsets2)")

let subsets3 = generateSubsets([])
print("Subsets of []: \(subsets3)")

Output:

Subsets of [1, 2]: [[], [2], [1], [1, 2]]
Subsets of [1, 2, 3]: [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
Subsets of []: [[]]
Program ended with exit code: 0

Xcode Screenshot: