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:

- It adds the current subset to the
`subsets`

array. - 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.

- It appends the element at the current index to the

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: