life is short - you need Python!

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, X, 0, 0, li.__len__())