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
Title: 77. Combination - LeetCode
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) {
res.add(new ArrayList<>(path));
return;
}
for (int i = begin; i <= n; i++) {
path.add(i);
dfs(path, i + 1);
path.remove(path.size() - 1); // to flash back
}
}
}
Combined total III
Title: 216. Combined total III - LeetCode
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) {
res.add(new ArrayList<>(path));
return;
}
for (int i = u; i <= 9; i++) {
sum += i;
path.add(i);
dfs(path, sum, i + 1);
sum -= i;
path.remove(path.size() - 1);
}
}
}
Letter combination of telephone numbers
Title: 17. Letter combination of telephone number - LeetCode
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()) {
res.add(path.toString());
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
Title: 39. Combined total - LeetCode
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) {
res.add(new ArrayList<>(path));
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];
path.add(candidates[i]);
dfs(path, sum, i);
sum -= candidates[i];
path.remove(path.size() - 1);
}
}
}
Combined total II
Title: 40. Combined total II - LeetCode
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) {
res.add(new ArrayList<>(path));
return;
}
for (int i = start; i < candidates.length; i++) {
// duplicate removal
if (i > start && candidates[i] == candidates[i - 1]) continue;
sum += candidates[i];
path.add(candidates[i]);
dfs(path, sum, i + 1);
sum -= candidates[i];
path.remove(path.size() - 1);
}
}
}
Separated palindrome string
Title: 131. Split palindrome string - LeetCode
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()) {
res.add(new ArrayList<>(path));
return;
}
for (int i = start; i < s.length(); i++) {
String ss = s.substring(start, i + 1); // cutting
if (isPalindrome(ss)) {
path.add(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());
}
}
Recover IP address
Title: 93. Restore IP address LeetCode
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;
public List<String> restoreIpAddresses(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) {
res.add(new ArrayList<>(path)); // Add results every time
for (int i = start; i < nums.length; i++) {
path.add(nums[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) {
res.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++) {
// Do not add duplicate elements
if (i != start && nums[i] == nums[i - 1]) continue;
path.add(nums[i]);
dfs(path, i + 1);
path.remove(path.size() - 1);
}
}
}
Longest increasing subsequence
Title: 491. Incremental subsequence - LeetCode
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
path.add(nums[i]);
dfs(path, i + 1);
path.remove(path.size() - 1);
}
}
}
Full arrangement
Title: 46. Full arrangement - LeetCode
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) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
path.add(nums[i]);
used[i] = true;
dfs(path, used, u + 1);
path.remove(path.size() - 1);
used[i] = false;
}
}
}
Full arrangement II
Title: 47. Full array II - LeetCode
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) {
res.add(new ArrayList<>(path));
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;
path.add(nums[i]);
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) {
res.add(new ArrayList<>(path));
return;
}
boolean[] tmpUsed = new boolean[21];
for (int i = 0; i < nums.length; i++) {
if (used[i] || tmpUsed[nums[i] + 10]) continue;
path.add(nums[i]);
used[i] = true;
tmpUsed[nums[i] + 10] = true;
dfs(path, used, i + 1);
path.remove(path.size() - 1);
used[i] = false;
}
}
}
Reschedule - hard
Title: 332. Rescheduling - LeetCode
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<>());
map.get(src).add(dst);
}
// 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());
res.add(0, src);
}
}
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]);
tmpList.add(sb.toString());
}
res.add(tmpList);
}
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
Title: 37. Solution independent force buckle (LeetCode)
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;
}
}