[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

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;
    }
}

Tags: Algorithm leetcode dfs

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