Code: Find all Subsets of an array using Recursion | DSA in C++ - Software Development PDF Download

Here's a code snippet in C++ that uses recursion to find all the subsets of an array:

#include <iostream>

#include <vector>

using namespace std;

// Recursive function to find subsets

void findSubsets(vector<int>& nums, vector<int>& subset, int index) {

    // Print the current subset

    for (int num : subset) {

        cout << num << " ";

    }

    cout << endl;

    // Generate subsets by including the current element

    for (int i = index; i < nums.size(); i++) {

        subset.push_back(nums[i]);

        findSubsets(nums, subset, i + 1);

        subset.pop_back();

    }

}

// Function to find subsets of an array

void subsets(vector<int>& nums) {

    vector<int> subset;

    findSubsets(nums, subset, 0);

}

// Main function

int main() {

    vector<int> nums = {1, 2, 3};

    subsets(nums);

    return 0;

}

Output:

1 

1 2 

1 2 3 

1 3 

2 

2 3 

3

Explanation:

• We define a helper function 'findSubsets' that takes three parameters: 'nums' (the input array), 'subset' (the current subset being generated), and 'index' (the current index of the element being considered).
• Inside the 'findSubsets' function, we first print the current subset by iterating over its elements and outputting them.
• Then, we generate subsets by including the current element at the given index. We start from the given index and iterate until the end of the input array.
• For each element, we add it to the 'subset' vector, recursively call the 'findSubsets' function with the updated 'subset' and the next index (i + 1), and then remove the last element from the 'subset' vector (backtracking).
• By doing this, we generate all possible subsets by either including or excluding each element at each recursive step.
• Finally, we define the 'subsets' function that initializes an empty 'subset' vector and calls the 'findSubsets' function with the input array and initial index 0.
• In the 'main' function, we create an example input array '{1, 2, 3}' and call the 'subsets' function.

The code uses recursion to explore all possible combinations of elements in the input array. At each step, we either include the current element in the subset or exclude it, leading to the generation of all possible subsets. The recursion stops when we reach the end of the input array, and we backtrack by removing the last element to explore other possibilities. The base case for the recursion is when we have processed all elements in the array, and at that point, we print the generated subset.

The output shows all the subsets of the input array '{1, 2, 3}'. Each line represents a different subset, and the numbers separated by spaces indicate the elements included in that particular subset.