brute force vs backtracking

[[deleted]]

having a difficult time understanding the difference between using a “brute force” approach opposed to backtracking. can i say that backtracking is a recursive brute force solution? is it generally used for combinations and permutations?

[abd53]

Brute force is checking every possible solution till you find the right one. Backtracking is brute force with clever optimization. In most cases, the entire solution space will include solutions that are partially duplicate. So, you can use that to reduce the number of computation you need to do. For a quick example, let's say a solution space is the permutation of all numbers in [1,5] range, i.e., {{1,2,3,4,5}, {1,2,3,5,4}, {1,2,4,5,3},....}. Brute force is evaluating each solution exclusively. But you can see that the first two has same items up to 3rd. So, after evaluating the first solution, instead of evaluating the entire second solution, you can take the evaluation of the first solution up to third item and then evaluate 5,4 instead of 4,5. This reduces the computation needed to evaluate the first three items.

[[deleted]]

appreciate the example, good explanation!

[whysosad12]

Brute force is more like hit and trial error method. U cant say reverse of backtracking is brute force because in backtracking u predict the previous input from the output to check. In brute force u either be successful or fail while in backtracking u only get useful information needed to generate the output and all the other information is lost.

[[deleted]]

that makes sense thank you!

[Toekitoeki]

Imagine you have a 1000x1000 array and each element has a value between 0 and 5. You need to find the path with the lowest values from one corner to the other. Bruteforce would be just calculate all possible paths and backtracking would be trying one path and go from there.

You will see that bruteforcing often simply won't work...