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<>();
LinkedList<Integer> path = new LinkedList<>();
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){
result.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++){
path.add(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<>();
LinkedList<Integer> path = new LinkedList<>();
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++) {
path.add(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()) {
list.add(temp.toString());
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) {
res.add(new ArrayList<>(path));
return;
}
for (int i = idx; i < candidates.length; i++) {
// Trim, terminate traversal if sum + candidates[i] > target
if (sum + candidates[i] > target) break;
path.add(candidates[i]);
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<>();
Deque<Integer> deque = new LinkedList<>();
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) {
lists.add(new ArrayList(deque));
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