generate all subsets using recursion | how to
Yesterday I wrote another program to generate all subsets of a set (array / list) during my preparation for today's class on backtracking at National Programming Camp. I wrote the code in C but just converted it into Python for the readers of the blog, so that they can understand and appreciate the beauty of recursion / backtracking. taken = [] def process(X): print X def generate_all_subsets(li, X, i, k, m): process(X[0:i]) for j in range(k, m): if taken[j] == False: if i > 0: if li[j] <= X[i-1]: continue taken[j] = True X.append(li[j]) generate_all_subsets(li, X, i+1, j+1, m) taken[j] = False X.pop(i) if __name__ == "__main__": li = [1, 2, 3, 4] X = [] taken.extend([False, False, False, False]) generate_all_subsets(li,