Backtracking is a powerful technique used to solve problems by exploring all possible solutions step by step. It works by incrementally building candidates to the solution and abandoning a candidate as soon as it is determined that it cannot lead to a valid solution.

Backtracking is often used when you need to find all possible solutions to a problem or optimize a solution based on certain constraints. The algorithm makes a series of choices, and if a choice leads to an invalid solution, it goes back to the previous choice and tries a different path.

Example: Generating Subsets

Suppose we have a set of integers and we want to generate all possible subsets of this set. We can use backtracking to solve this problem.

Here’s a Swift implementation that generates all subsets using backtracking:

func generateSubsets(_ set: [Int]) -> [[Int]] {
    var subsets = [[Int]]()
    var currentSubset = [Int]()

    func backtrack(_ index: Int) {
        // Add the current subset to the result
        subsets.append(currentSubset)

        // Explore all possible choices from the current index
        for i in index..<set.count {
            currentSubset.append(set[i])
            backtrack(i + 1)
            currentSubset.removeLast()
        }
    }

    backtrack(0)
    return subsets
}

// Example usage
let set = [1, 2, 3]
let allSubsets = generateSubsets(set)
print(allSubsets)

In this implementation, we start with an empty array subsets to store all the generated subsets and an empty array currentSubset to represent the current subset being built.

The backtrack function is the core of the backtracking algorithm. It takes the current index as a parameter and does the following:

1. It adds the current subset to the subsets array.
2. It explores all possible choices from the current index onwards. For each choice:
   • It appends the element at the current index to the currentSubset.
   • It recursively calls backtrack with the next index.
   • It removes the last element from currentSubset to backtrack and try the next choice.

Finally, we call the backtrack function with the initial index 0 to start the backtracking process. The function explores all possible subsets and returns the array of generated subsets.

When we run this code with the example set [1, 2, 3], it will output all possible subsets:

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

Problems

22. Generate Parentheses

Leetcode: 22. Generate Parentheses

func generateParenthesis(_ n: Int) -> [String] {
  guard n > 0 else { return [] }
  guard n > 1 else { return ["()"] }
  var res = [String]()

  func dfs(_ numberOfOpenBracket: Int, _ numberOfCloseBracket: Int, _ s: String) {
      // Base case: we have exactly n closing ")" -> done
      if numberOfCloseBracket == n { res.append(s); return }

      // we can add more "("
      if numberOfOpenBracket < n { dfs(numberOfOpenBracket + 1, numberOfCloseBracket, s + "(") }

      // we can add more ")"
      if numberOfCloseBracket < numberOfOpenBracket { dfs(numberOfOpenBracket, numberOfCloseBracket + 1, s + ")") }
  }

  // have to start with "("
  dfs(1, 0, "(")

  return res
}

print(generateParenthesis(1))
// ["()"]

print(generateParenthesis(2))
// ["(())", "()()"]

print(generateParenthesis(3))
// ["((()))", "(()())", "(())()", "()(())", "()()()"]

Conclusion

Backtracking is a versatile technique that can be used to solve various problems by exploring all possible solutions incrementally. It allows us to efficiently search through a large solution space by pruning invalid solutions early on.

Further Readings:

• Leetcode - Backtracking