LeetCode Day 24 Backtracking Algorithm (1/6)

After finished binary tree, now move to backtracking algrithm practice

1.Element knowledges

1.1 Backtracking

Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.

1.2 Efficiency

The essence of backtracking is exhaustive, exhaust all possible, and then select the answer we want, if you want to make the backtracking method more efficient, you can add some pruning operations, but it does not change the backtracking method is the essence of the exhaustive.

1.3 Application of backtracking

• Combination problem: find the set of k numbers inside N numbers according to a certain rule
• Cutting problem: how many ways can a string be cut according to certain rules?
• Subset problem: How many subsets of a set of N numbers are there?
• Arrangement problem: N numbers according to a certain rule, how many ways to arrange the whole arrangement
• Board problems: N queens, solving sudoku, etc.

1.4 Pseudocode

In order to apply backtracking to a specific class of problems, one must provide the data P for the particular instance of the problem that is to be solved, and six procedural parameters, root, reject, accept, first, next, and output. These procedures should take the instance data P as a parameter and should do the following:

1. root(P): return the partial candidate at the root of the search tree.
2. reject(P,c): return true only if the partial candidate c is not worth completing.
3. accept(P,c): return true if c is a solution of P, and false otherwise.
4. first(P,c): generate the first extension of candidate c.
5. next(P,s): generate the next alternative extension of a candidate, after the extension s.
6. output(P,c): use the solution c of P, as appropriate to the application.

The backtracking algorithm reduces the problem to the call backtrack(root(P)), where backtrack is the following recursive procedure:

procedure backtrack(P, c) is
    if reject(P, c) then return
    if accept(P, c) then output(P, c)
    s ← first(P, c)
    while s ≠ NULL do
        backtrack(P, s)
        s ← next(P, s)

2. Question 1

77. Combinations

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

You may return the answer in any order.

This can be solved with nested for loops, also known as Brute Force, but this creates a problem in that as k gets larger, the number of layers of nested for loops increases, and when k is 50, O(n^50) will be a disaster.

This is where the idea of recursion comes in handy.

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = [] 
        self.backtracking(n, k, 1, [], result)
        return result
    def backtracking(self, n, k, startIndex, path, result):
        if len(path) == k:
            result.append(path[:])
            return
        for i in range(startIndex, n + 1):  
            path.append(i)  
            self.backtracking(n, k, i + 1, path, result)
            path.pop()