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.



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

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.