Experiments with using backtracking for generating subsets of n.

jwasham · jwasham · commit 034f1594b419 · 2016-08-25T12:42:03.000-07:00
diff --git a/backtracking/subsets.py b/backtracking/subsets.py
@@ -0,0 +1,62 @@
+"""
+Generates all subsets
+"""
+import sys
+
+
+# def is_solution(k, n):
+#     return k == n
+#
+#
+# def construct_candidates():
+#     return [0, 1]
+#
+#
+# def process_solution(working_set):
+#     global solutions
+#
+#     s = {k for k in working_set if working_set[k] == 1}
+#     solutions.append(s)
+#
+#
+# def backtrack(working_set, k, n):
+#
+#     if is_solution(k, n):
+#         process_solution(working_set)
+#     else:
+#         k += 1
+#         candidates = construct_candidates()
+#         for i in candidates:
+#             working_set[k] = i
+#             backtrack(working_set, k, n)
+
+
+def backtrack_compact(working_set, k, n):
+    global solutions
+
+    if k == n:
+        s = {k for k in working_set if working_set[k] == 1}
+        solutions.append(s)
+    else:
+        k += 1
+        for i in [0, 1]:
+            working_set[k] = i
+            backtrack_compact(working_set, k, n)
+
+
+def main():
+    # n = sys.argv[1]
+    n = 2
+
+    global solutions
+    solutions = []
+
+    # backtrack({}, 0, n)
+    # print(solutions)
+
+    backtrack_compact({}, 0, n)
+    print(solutions)
+
+
+if __name__ == '__main__':
+    main()
