# [code Capriccio] backtracking algorithm

Video: Take you through the backtracking algorithm (Theory)
Reference documents: Code caprice (programercall. Com)

The backtracking method can generally solve the following problems:

• Combinatorial problem: find the set of k numbers from N numbers according to certain rules
• Arrangement problem: N numbers are all arranged according to certain rules. There are several arrangement modes
• Cutting problem: there are several cutting methods for a string according to certain rules
• Subset problem: how many subsets meet the conditions in a set of N numbers
• Chess board problem: Queen N, Sudoku

Disordered combination and orderly arrangement

Backtracking algorithm template framework:

```void backtracking(parameter) {
if (Termination conditions) {
Storage results;
return;
}

for (Selection: Elements in the set of this layer (the number of children of nodes in the tree is the size of the set)) {
Processing node;
backtracking(Path, selection list); // recursion
Backtracking and cancellation processing results
}
}
```

## combination

Given two integers n and k, returns the combination of all possible k numbers in the range [1, n].

You can return the answers in any order.

```Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
```

```class Solution {
List<List<Integer>> res = new ArrayList<>();
int n, k;

public List<List<Integer>> combine(int n, int k) {
this.n = n;
this.k = k;
dfs(new ArrayList<>(), 1);
return res;
}

void dfs(List<Integer> path, int begin) {
if (path.size() == k) {
return;
}
for (int i = begin; i <= n; i++) {
dfs(path, i + 1);
path.remove(path.size() - 1); // to flash back
}
}
}
```

## Combined total III

Find the combination of all k numbers whose sum is n, and satisfy the following conditions:

• Use only numbers 1 to 9
• Each number can be used at most once

Returns a list of all possible valid combinations. The list cannot contain the same combination twice, and the combination can be returned in any order.

```input: k = 3, n = 7
output: [[1,2,4]]
explain:
1 + 2 + 4 = 7
There are no other matching combinations.
```
```class Solution {
List<List<Integer>> res = new ArrayList<>();
int k, n;

public List<List<Integer>> combinationSum3(int k, int n) {
this.k = k;
this.n = n;
dfs(new ArrayList<>(), 0, 1);
return res;
}

void dfs(List<Integer> path, int sum, int u) {
if (sum > n) return; // prune
if (sum == n && path.size() == k) {
return;
}
for (int i = u; i <= 9; i++) {
sum += i;
dfs(path, sum, i + 1);
sum -= i;
path.remove(path.size() - 1);
}
}
}
```

## Letter combination of telephone numbers

Standard backtracking template + StringBuilder:

```class Solution {
Map<Integer, String> map = Map.of(
2, "abc", 3, "def", 4, "ghi", 5, "jkl",
6, "mno", 7, "pqrs", 8, "tuv", 9, "wxyz");
List<String> res = new ArrayList<>();
String digits;

public List<String> letterCombinations(String digits) {
if (digits.length() == 0) return res;
this.digits = digits;
dfs(new StringBuilder(), 0);
return res;
}

void dfs(StringBuilder path, int idx) {
if (idx == digits.length()) {
return;
}
String letters = map.get(digits.charAt(idx) - '0');
for (int i = 0; i < letters.length(); i++) {
path.append(letters.charAt(i));
dfs(path, idx + 1);
path.deleteCharAt(path.length() - 1);
}
}
}
```

## Combined total I

Give you an integer array candidates without duplicate elements and a target integer target, find out all the different combinations of candidates that can make the number and the target number target, and return them in the form of a list. You can return these combinations in any order.

The same number in candidates can be selected repeatedly without limitation. If the selected number of at least one number is different, the two combinations are different.

For a given input, it is guaranteed that the number of different combinations of sum as target is less than 150.

```Input: candidates = [2,3,6,7], target = 7
Output:[[2,2,3],[7]]
Explanation:
2 And 3 can form a group of candidates, 2 + 2 + 3 = 7 . Note 2 can be used multiple times.
7 Also a candidate, 7 = 7 .
There are only two combinations.
```
```class Solution {
List<List<Integer>> res = new ArrayList<>();
int [] candidates;
int target;

public List<List<Integer>> combinationSum(int[] candidates, int target) {
this.candidates = candidates;
this.target = target;
Arrays.sort(this.candidates); // Premise of pruning
dfs(new ArrayList<>(), 0, 0);
return res;
}

void dfs(List<Integer> path, int sum, int start) {
// if (sum > target) return;
if (sum == target) {
return;
}
for (int i = start; i < candidates.length; i++) {
// If the sum of the next layer is larger than the target, no subsequent recursion is required
if (sum + candidates[i] > target) break;
sum += candidates[i];
dfs(path, sum, i);
sum -= candidates[i];
path.remove(path.size() - 1);
}
}
}
```

## Combined total II

Given a set of candidates with candidate numbers and a target number target, find out all combinations in the candidates that can make the sum of numbers the target.

Each number in candidates can only be used once in each combination.

Note: the solution set cannot contain duplicate combinations.

```input: candidates = [10,1,2,7,6,1,5], target = 8,
output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
```
```class Solution {
List<List<Integer>> res = new ArrayList<>();
int[] candidates;
int target;

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
this.candidates = candidates;
this.target = target;
dfs(new ArrayList<>(), 0, 0);
return res;
}

void dfs(List<Integer> path, int sum, int start) {
if (sum > target) return;
if (sum == target) {
return;
}
for (int i = start; i < candidates.length; i++) {
// duplicate removal
if (i > start && candidates[i] == candidates[i - 1]) continue;
sum += candidates[i];
dfs(path, sum, i + 1);
sum -= candidates[i];
path.remove(path.size() - 1);
}
}
}
```

## Separated palindrome string

Give you a string s. please divide s into some substrings so that each substring is a palindrome string. Returns all possible partition schemes of S.

Palindrome string is a string that is read forward and read backward.

```Input: s = "aab"
Output:[["a","a","b"],["aa","b"]]
```
```class Solution {
List<List<String>> res = new ArrayList<>();

public List<List<String>> partition(String s) {
dfs(s, new ArrayList<>(), 0);
return res;
}

void dfs(String s, List<String> path, int start) {
if (start == s.length()) {
return;
}
for (int i = start; i < s.length(); i++) {
String ss = s.substring(start, i + 1); // cutting
if (isPalindrome(ss)) {
dfs(s, path, i + 1);
path.remove(path.size() - 1);
}
}
}

// Determine whether it is palindrome string
boolean isPalindrome(String s) {
return s.equals(new StringBuilder(s).reverse().toString());
}
}
```

A valid IP address consists of exactly four integers (each integer is between 0 and 255 and cannot contain a leading 0). Use '.' between integers separate.

• For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and“ 192.168@1.1 "Is an invalid IP address.

Given a string s containing only numbers to represent an IP address and return all possible valid IP addresses, these addresses can be obtained by inserting '.' in S To form. You cannot reorder or delete any numbers in S. You can return the answers in any order.

```Input: s = "25525511135"
Output:["255.255.11.135","255.255.111.35"]

Input: s = "0000"
Output:["0.0.0.0"]
```
```class Solution {
List<String> res = new ArrayList<>();
String s;

this.s = s;
dfs("", 0, 0);
return res;
}

void dfs(String path, int start, int cnt) {
// Prune according to IP address length
if (12 - cnt * 3 < s.length() - path.length()) return;
if (cnt == 4 && path.length() >= s.length() + 4) {
res.add(path.substring(0, path.length() - 1)); // Remove the last
return;
}
for (int i = start; i < s.length(); i++) {
String ss = s.substring(start, i + 1);
if (ss.equals("0") || !ss.startsWith("0") && ss.length() <= 3 && Integer.parseInt(ss) <= 255) {
path += ss + ".";
dfs(path, i + 1, cnt + 1);
path = path.substring(0, path.length() - ss.length() - 1);
}
}
}
}
```

Other ways to write the retrospective part:

```for (int i = start; i < s.length(); i++) {
String ss = s.substring(start, i + 1);
if (ss.equals("0") || !ss.startsWith("0") && ss.length() <= 3 && Integer.parseInt(ss) <= 255) {
dfs(path + ss + ".", i + 1, cnt + 1);
}
}
```

## Subset I

Title: 78. Subset - LeetCode

Give you an integer array nums. The elements in the array are different from each other. Returns all possible subsets (power sets) of the array.

The solution set cannot contain duplicate subsets. You can return the solution set in any order.

```Input: nums = [1,2,3]
Output:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
```
```class Solution {
List<List<Integer>> res = new ArrayList<>();
int[] nums;

public List<List<Integer>> subsets(int[] nums) {
this.nums = nums;
dfs(new ArrayList<>(), 0);
return res;
}

void dfs(List<Integer> path, int start) {

for (int i = start; i < nums.length; i++) {
dfs(path, i + 1);
path.remove(path.size() - 1);
}
}
}
```

## Subset II

Title: 90. Subset II - LeetCode

Give you an integer array nums, which may contain duplicate elements. Please return all possible subsets (power sets) of this array.

The solution set cannot contain duplicate subsets. The subsets in the returned solution set can be arranged in any order.

```Input: nums = [1,2,2]
Output:[[],[1],[1,2],[1,2,2],[2],[2,2]]
```
```class Solution {
List<List<Integer>> res = new ArrayList<>();
int[] nums;

public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums); // Precondition for checking element repetition
this.nums = nums;
dfs(new ArrayList<>(), 0);
return res;
}

void dfs(List<Integer> path, int start) {
for (int i = start; i < nums.length; i++) {
// Do not add duplicate elements
if (i != start && nums[i] == nums[i - 1]) continue;
dfs(path, i + 1);
path.remove(path.size() - 1);
}
}
}
```

## Longest increasing subsequence

Give you an integer array nums, find and return all the different increment subsequences in the array, and there are at least two elements in the increment subsequence. You can return the answers in any order.

The array may contain duplicate elements. If two integers are equal, it can also be regarded as a special case of the incremental sequence.

```Input: nums = [4,6,7,7]
Output:[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
```
```class Solution {
List<List<Integer>> res = new ArrayList<>();
int[] nums;

public List<List<Integer>> findSubsequences(int[] nums) {
this.nums = nums;
dfs(new ArrayList<>(), 0);
return res;
}

void dfs(List<Integer> path, int start) {
if (path.size() >= 2) res.add(new ArrayList<>(path));
// Create a new hash table for each layer for deduplication
boolean[] used = new boolean[201]; // The tag has been used
for (int i = start; i < nums.length; i++) {
// The condition of increment must be met
if (!path.isEmpty() && nums[i] < path.get(path.size() - 1)
|| used[nums[i] + 100]) continue;
used[nums[i] + 100] = true; // The tag is already in use
dfs(path, i + 1);
path.remove(path.size() - 1);
}
}
}
```

## Full arrangement

Given an array nums without duplicate numbers, all possible permutations are returned. You can return the answers in any order.

```Input: nums = [1,2,3]
Output:
[[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]]
```
```class Solution {
List<List<Integer>> res = new ArrayList<>();
int[] nums;

public List<List<Integer>> permute(int[] nums) {
this.nums = nums;
dfs(new ArrayList<>(), new boolean[nums.length], 0);
return res;
}

void dfs(List<Integer> path, boolean[] used, int u) {
if (u == nums.length) {
return;
}

for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
dfs(path, used, u + 1);
path.remove(path.size() - 1);
used[i] = false;
}
}
}
```

## Full arrangement II

Given a sequence nums that can contain repeated numbers, return all non repeated full permutations in any order.

```Input: nums = [1,1,2]
Output:
[[1,1,2],
[1,2,1],
[2,1,1]]
```

Method 1: use nums[i] == nums[i - 1] to remove duplicates

```class Solution {
List<List<Integer>> res = new ArrayList<>();
int[] nums;

public List<List<Integer>> permuteUnique(int[] nums) {
this.nums = nums;
Arrays.sort(nums);
dfs(new ArrayList<>(), new boolean[nums.length], 0);
return res;
}

void dfs(List<Integer> path, boolean[] used, int start) {
if (path.size() == nums.length) {
return;
}

for (int i = 0; i < nums.length; i++) {
// duplicate removal
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1]) continue;

if (used[i]) continue;
used[i] = true;
dfs(path, used, i + 1);
path.remove(path.size() - 1);
used[i] = false;
}
}
}
```

Method 2: use tmpUsed array for deduplication

```// Use tmpUsed array to remove duplicates
class Solution2 {
List<List<Integer>> res = new ArrayList<>();
int[] nums;

public List<List<Integer>> permuteUnique(int[] nums) {
this.nums = nums;
dfs(new ArrayList<>(), new boolean[nums.length], 0);
return res;
}

void dfs(List<Integer> path, boolean[] used, int start) {
if (path.size() == nums.length) {
return;
}

boolean[] tmpUsed = new boolean[21];
for (int i = 0; i < nums.length; i++) {
if (used[i] || tmpUsed[nums[i] + 10]) continue;
used[i] = true;
tmpUsed[nums[i] + 10] = true;
dfs(path, used, i + 1);
path.remove(path.size() - 1);
used[i] = false;
}
}
}
```

## Reschedule - hard

```class Solution {
List<String> res = new ArrayList<>();
Map<String, PriorityQueue<String>> map = new HashMap<>();

public List<String> findItinerary(List<List<String>> tickets) {
for (List<String> ticket : tickets) {
String src = ticket.get(0), dst = ticket.get(1);
if (!map.containsKey(src))
map.put(src, new PriorityQueue<>());
}
// View stored data
// map.forEach((k, v) -> {
//     System.out.print("k = " + k + "  ");
//     v.forEach(e -> System.out.print(" v = " + e + " "));
//     System.out.println();
// });
dfs("JFK");
return res;
}

void dfs(String src) {
PriorityQueue<String> pq = map.get(src);
while (pq != null && !pq.isEmpty())
dfs(pq.poll());
}
}
```

## N Queen - hard

Title: 51. N Queen - LeetCode

```class Solution {
final int N = 20;
List<List<String>> res = new ArrayList<>();
char[][] g = new char[N][N];
boolean[] col = new boolean[N]; // Whether a row has been accessed
boolean[] dg = new boolean[N]; // Has the diagonal been visited
boolean[] udg = new boolean[N]; // Has the opposite corner been accessed
int n;

public List<List<String>> solveNQueens(int n) {
// Initialize to
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
g[i][j] = '.';
this.n = n;
dfs(0); // Start on line 0
return res;
}

// Currently traversed row
void dfs(int u) {
if (u == n) {
List<String> tmpList = new ArrayList<>();
for (int i = 0; i < n; i++) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < n; j++)
sb.append(g[i][j]);
}
}
int x = u;
for (int y = 0; y < n; y++) {
if (col[y] || dg[y - x + n] || udg[y + x]) continue;
col[y] = dg[y - x + n] = udg[y + x] = true;
g[x][y] = 'Q';
dfs(x + 1);
col[y] = dg[y - x + n] = udg[y + x] = false;
g[x][y] = '.';
}
}
}
```

## Sudoku - hard

```class Solution {
public void solveSudoku(char[][] board) {
dfs(board);
}

boolean dfs(char[][] board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') continue;
// Try a number from 1 to 9
for (char n = '1'; n <= '9'; n++) {
if (check(board, i, j, n)) {
board[i][j] = n; // Fill in numbers
// Find the solution and return directly
if (dfs(board)) return true;
board[i][j] = '.'; // to flash back
}
}
return false; // I've tried all nine figures
}
}
return true; // After normal traversal, the solution is found
}

// Is it legal to place k at board[x][y]
boolean check(char[][] board, int x, int y, int k) {
// Check whether the current column and row are legal
for (int i = 0; i < 9; i++)
if (board[i][y] == k || board[x][i] == k)
return false;
// Check whether the current 3x3 intrauterine position is legal and locate it to the 3x3 intrauterine position
// (XX, YY) upper left corner of 3x3 palace, (XX + 2, YY + 2) lower right corner of 3x3 Palace
int xx = x / 3 * 3, yy = y / 3 * 3;
for (int i = xx; i <= xx + 2; i++)
for (int j = yy; j <= yy + 2; j++)
if (board[i][j] == k) return false;
return true;
}
}
```

Tags: Algorithm leetcode dfs

Posted by tmharrison on Tue, 06 Sep 2022 01:42:00 +0930