Brute-force search, also called complete search, solves a problem by traversing its entire search space until it finds a solution. It may prune branches proven unable to produce the required result. section 4.2.1
The method provides a baseline for algorithm design: enumerate candidate solutions, test or construct each one, and stop when the search reaches the required condition. Recursive and iterative implementations can express the same search. section 4.2.1
Recognize brute-force search by its role among common problem-solving paradigms:
- Complete search examines the whole search space, unlike greedy methods that select locally optimal choices. section 1.5.2
- Divide and conquer separates independent subproblems, while dynamic programming reuses solutions to overlapping subproblems in a table. section 4.5
Generating subsets
For a set of size n, a recursive search branches on whether each element belongs to the current subset and prints a subset when the required size is reached. An iterative bit-sequence method enumerates the same choices using the bit patterns from 0 through 2ⁿ−1; the supplied implementation demonstrates both approaches for n = 4. section 4.2.1
Listing 4.1 Subset generation
def search(k, n):
if (k == n):
print(subset) #1
else:
search(k+1, n)
subset.append(k)
search(k+1, n)
subset.pop()
#end if
def bitseq(n):
for b in range(1 << n):
subset = []
for i in range(n):
if (b & 1 << i):
subset.append(i)
#end for
print(subset)
#end for
if __name__ == "__main__":
n = 4
subset = []
search(0, n) #2
subset = []
bitseq(n) #3
Inspect the from-scratch Python listing for recursive subset search, branch backtracking, termination, and iterative bit-sequence enumeration. section 4.2.1
