Interview Question

Software Engineer Intern Interview(Student Candidate) Palo Alto, CA

Write a function that prints out all subsets of a given set

  of numbers.
Answer

Interview Answer

2 Answers

0

def subsets(lst):
    if(len(lst) == 1):
        return [lst]
    else:
        a = subsets(lst[1:])
        c = [[lst[0]]]
        for elem in a:
            b = elem + [lst[0]]
            c.append(elem)
            c.append(b)
        return c

Sanchit Bareja on Feb 13, 2012
0

Here's my rough draft:

vector<vector<int>> getSubsets(vector<int>& input){

if(input.size() == 1){
vector<int> base(2);
base.push_back(input[0]);
base.push_back(void);

vector<vector<int>> re(1);
re.push_back(base);
return re;
}

int current = input[0];
input.erase(input.begin());
vector<vector<int>> subsets = getSubsets(input);
int size = subsets.size();
for(int i = 0; i< size; i++){
  vector<int> set = subsets[i];
  set.push_back(current);
  subsets.push_back(set);
}

return subsets;

}

An explanation can be found here: http://stackoverflow.com/questions/728972/finding-all-the-subsets-of-a-set

Tommy on Nov 7, 2012

Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up