Write a method to return all subsets of a set

Problem

Write a method to return all subsets of a set.

For example, given set of characters, A = { a, b, c, d}
The output should be as blow:

['a', 'ab', 'abc', 'abcd', 'abd', 'ac', 'acd', 'ad', 'b', 'bc', 'bcd', 'bd', 'c', 'cd', 'd']

Ansewer

Depth First approach with Backtracking, O(N!)

Since the order of the element in the set is not important, we can perform the DFS through the input as if the input set is a tree.

Backtracking is necessary to traverse all the elements in the tree.

The running time of this algorithm will be $O(N!)$. I will try to look for a faster algorithm than this one.
Here is the complete code.

	#include<vector>
	#include<string>
	#include<iostream>
	using namespace std;
	void find(string& input, string cur, int pos, vector<string>&subset)
	{
	if (cur.length())
	subset.push_back(cur);
	if (pos == input.size())
	return;
	for(int i = pos; i < input.length(); i++)
	{
	cur.push_back(input[i]);
	find(input, cur, i+1, subset);
	cur.pop_back();
	}
	}
	vector<string> find_all_subset(string input)
	{
	vector<string> subset;
	find(input, "", 0, subset);
	return subset;
	}
	int main()
	{
	string input = "abcd";
	vector<string> result = find_all_subset(input);
	for (int i =0; i <result.size(); i++)
	cout<<result[i]<< ", "<<endl;
	return 1;
	}

view raw find_all_subset.cpp hosted with ❤ by GitHub

Practice statistics

19:00: to write up the code (one logical flaw was not found initially.)

Tried again on 04/25/2019.

Used DFS with backtracking.

 Solution in python

	'''
	Write a method to return all subsets of a set.
	For example, given set of characters, A = { a, b, c, d}
	The output should be as blow:
	['a', 'ab', 'abc', 'abcd', 'abd', 'ac', 'acd', 'ad', 'b', 'bc', 'bcd', 'bd', 'c', 'cd', 'd']
	25:36: to write the complete code. Initially, thought about DFS but got confused and did not choose it.
	that cost time. Later, change to DFS to solve it
	2:00: fix to typo. I should've gottn it before running it !!
	'''
	class SubSetFinder:
	def __init__(self):
	self.result = []
	def find_subset(self, input):
	self.search_subset(0, "", input)
	return self.result
	def search_subset(self, pos, current ,input):
	if len(current) > 0:
	self.result.append(current)
	for i in range(pos, len(input)):
	current += input[i]
	self.search_subset(i+1, current, input)
	current = current[:len(current)-1]
	p = SubSetFinder()
	input = ['a', 'b', 'c', 'd']
	print("input = {} result = {}".format(input, p.find_subset(input)))

view raw find_all_subset_in_string.py hosted with ❤ by GitHub

Practice statistics

25:36: to write the complete code. Initially, thought about DFS but got confused and did not choose it. that cost time. Later, change to DFS to solve it

2:00: fix to a typo. I should've gotten it before running it !!

UPDATE(2022-06-12): Solved the problem again. Got confused about what's the expected result. 

	def find_subset(input, subset ,pos, result):
	if len(subset) > 0:
	result.append("".join(subset))
	for i in range(pos, len(input)):
	subset.append(input[i])
	find_subset(input, subset, i + 1, result)
	subset.pop()
	def dfs(input):
	result = []
	find_subset(input, [], 0, result)
	return result
	input = 'abcd'
	result = dfs(input)
	print("subsets = {}".format(result))

view raw find_subsets_dfs.py hosted with ❤ by GitHub