# Retrospective Topic Solution and Example

Summary from Code casual backtracking

#### What's the use of backtracking?

Backtracking = Endless, it is always possible to use backtracking when you need to keep making choices and try all the choices to find a solution.

For example:

• Combination Problem: Find a set of k numbers in N numbers according to certain rules
• Cutting Problem: There are several ways to cut a string according to a certain rule
• Subset problem: how many eligible subsets are in a set of N numbers
• Arrangement problem: N numbers are arranged in a regular way, there are several ways to arrange them
• Chess board questions: Queen N, Solution Sudoku, etc.

In addition, it is helpful to simulate backtracking first when solving dynamic programming algorithm problems.

#### What does backtracking look like?

Recursion can be modeled using a tree structure, because backtracking resolves the problem of recursively finding a subset in a set, the size of the set = the width of the tree, and the depth of the recursion = the depth of the tree.

#### How to use backtracking:

Template for backtracking (important):

```void backtracking(parameter) {
if (Termination Conditions) {
Store results;
return;
}

for (Selection: Elements in the collection at this level (the number of children at nodes in the tree is the size of the collection)) {
Processing Node;
backtracking(Path, select list); // recursion
Retrospective, Undo Processing Result
}
}

```

Fill in the template in the following three sections to usually get an answer.

• Backtrace function template return values and parameters
• Termination condition of backtrace function
• Retrospective search traversal

#### Backward problem solving:

Combination classes:

If it's a set to combine, you need a startIndex, multiple sets to combine, and no startindex.

Duplicate values, startIndex++, are not allowed in backtracking; duplicate values are allowed and startIndex is not moved.

If there are duplicate values within a set, an auxiliary array is required.

Deducting 77 Questions : Given two integers n and k, returns the combination of all possible K numbers in 1...n.

```class Solution {
List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
combineHelper(n, k, 1);
return result;
}

/**
* Each time an element is selected from a set, the range of choices shrinks as the selection proceeds. Adjusting the range of choices depends on the startIndex
* @param startIndex Used to record where a collection begins to traverse in this layer's recursion (set is [1,...,n]).
*/
private void combineHelper(int n, int k, int startIndex){
//Termination Conditions
if (path.size() == k){
return;
}
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++){
combineHelper(n, k, i + 1);
path.removeLast();
}
}
}
```

Deducting 216 Questions : Find all combinations of k numbers that add up to n. Only positive integers with 1-9 are allowed in combinations, and there are no duplicate numbers in each combination.

```class Solution {
List<List<Integer>> result = new ArrayList<>();

public List<List<Integer>> combinationSum3(int k, int n) {
backTracking(n, k, 1, 0);
return result;
}

private void backTracking(int targetSum, int k, int startIndex, int sum) {
// Branch reduction
if (sum > targetSum) {
return;
}

if (path.size() == k) {
if (sum == targetSum) result.add(new ArrayList<>(path));
return;
}

// Branch reduction 9 - (k-path.size()) + 1
for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
sum += i;
backTracking(targetSum, k, i + 1, sum);
//To flash back
path.removeLast();
//To flash back
sum -= i;
}
}
}
```

Seventeen Tips : Given a string containing only the numbers 2-9, return all the combinations of letters it can represent.

```class Solution {

//Set the global list to store the final result
List<String> list = new ArrayList<>();

public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) {
return list;
}
//Initially corresponds to all digits, two new invalid strings have been added to correspond directly to 2-9
String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
//Iterative Processing
backTracking(digits, numString, 0);
return list;

}

//Each iteration gets a string, so a lot of string splicing is designed, so here's a more efficient StringBuild
StringBuilder temp = new StringBuilder();

//For example, if digits is "23" and num is 0, str represents 2 corresponding abc
public void backTracking(String digits, String[] numString, int num) {
//String resulting from traversing all records once
if (num == digits.length()) {
return;
}
//str represents the string corresponding to the current num
String str = numString[digits.charAt(num) - '0'];
for (int i = 0; i < str.length(); i++) {
temp.append(str.charAt(i));
backTracking(digits, numString, num + 1);
//Remove last attempt
temp.deleteCharAt(temp.length() - 1);
}
}
}
```

Deducting 39 Questions : Given an array of candidates with no duplicate elements and a target number, find all combinations of candidates that can make numbers and targets.

Numbers in candidates can be selected repeatedly without restriction.

```class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(candidates); // Sort first
backtracking(res, new ArrayList<>(), candidates, target, 0, 0);
return res;
}

public void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {
// Found a combination of numbers and target s
if (sum == target) {
return;
}

for (int i = idx; i < candidates.length; i++) {
// Trim, terminate traversal if sum + candidates[i] > target
if (sum + candidates[i] > target) break;
backtracking(res, path, candidates, target, sum + candidates[i], i);
path.remove(path.size() - 1); // Backtrace, removing the last element of the path
}
}
}
```

Deduct 40 Questions : Given an array of candidates and a target number, find all combinations of candidates that can make numbers and targets.

Each number in candidates can only be used once in each combination. Note: All numbers, including the target number, are positive integers. Unset cannot contain duplicate combinations.

```class Solution {
List<List<Integer>> lists = new ArrayList<>();
int sum = 0;

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
//To put all the duplicate numbers together, sort them first
Arrays.sort(candidates);
//Flagged array to help determine if a peer node has been traversed
boolean[] flag = new boolean[candidates.length];
backTracking(candidates, target, 0, flag);
return lists;
}

public void backTracking(int[] arr, int target, int index, boolean[] flag) {
if (sum == target) {
return;
}
for (int i = index; i < arr.length && arr[i] + sum <= target; i++) {
//Duplicate node appears, the first node in the same layer has been visited, so skip directly
if (i > 0 && arr[i] == arr[i - 1] && !flag[i - 1]) {
continue;
}
flag[i] = true;
sum += arr[i];
deque.push(arr[i]);
//Each node can only be selected once, so start from the next
backTracking(arr, target, i + 1, flag);
int temp = deque.pop();
flag[i] = false;
sum -= temp;
}
}
}
```

Continue further - 10.14

Keywords: Algorithm

Added by twister47 on Thu, 14 Oct 2021 22:51:56 +0300