DSCoding/PowerSet.h at master · shazzing/DSCoding · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//
//  PowerSet.h
//  Recursion
//
//  Created by shashank hegde on 12/19/15.
//  Copyright (c) 2015 shashank hegde. All rights reserved.
//

#ifndef Recursion_PowerSet_h
#define Recursion_PowerSet_h
#include <vector>

using namespace std;

void powerSetHelper(const vector<int>& input, int toBeSelected, vector<int>* selectedSoFar, vector<vector<int>>* result)
{
    if(toBeSelected == input.size())
    {
        result->emplace_back(*selectedSoFar);
        return;
    }
    selectedSoFar->emplace_back(input[toBeSelected]);
    powerSetHelper(input, toBeSelected+1, selectedSoFar, result);
    selectedSoFar->pop_back();
    // get the elements without tobeSelected element this time.
    powerSetHelper(input, toBeSelected +1, selectedSoFar, result);
}


vector<vector<int>> powerSet(const vector<int>& inp)
{
    vector<vector<int>> powerSetRes;
    vector<int> selectedSoFar;
    powerSetHelper(inp, 0, &selectedSoFar, &powerSetRes);
    return powerSetRes;
}

#endif