A backtracking algorithm is one that runs through every possibility, and each one has a different result

To solve a backtracking problem is actually to solve a decision tree traversal process

We need to think about three questions:

  • Path: The path that has been made to store the result in the future
  • Selection list: Currently available choices
  • End condition: is the condition when the traversal reaches the end

There is a framework for solving backtracking algorithms:

LinkedList<LinkedList< element type >> Result set =new LinkedList<>();
private void backtrack(Path, selection list) {
    for(Element type O: select list) {if(at the end) {add the selection list to the result set; } make a choice; Backtrack, list of choices Undo selection; }}Copy the code

The core framework of the backtracking algorithm is this pseudo-code, which recurses through the loop, makes a selection before the recursion, undoes the selection after the recursion, and adds the selection to the result set at the end

Using backtracking, the full permutation problem can be realized:

import java.util.LinkedList;

public class Test {

	private static LinkedList<LinkedList<Integer>> res = new LinkedList<>();
	
	public static void main(String[] args) {
		int[] nums = {1.2.3.4.5.6.7.8};
		LinkedList<LinkedList<Integer>> list = permutation(nums);
		System.out.println(list.size());
	}
	
	private static LinkedList<LinkedList<Integer>> permutation(int[] nums) {
		LinkedList<Integer> track = new LinkedList<>();
		backtrack(nums, track);
		return res;
	}
	
	private static void backtrack(int[] nums, LinkedList<Integer> track) {
		
		// If the end is reached, the result is added to the RES list
		if (nums.length == track.size()) {
			res.add(new LinkedList<>(track));
			return;
		}
		
		for (int i : nums) {
			
			// Skip if you have traversed
			if (track.contains(i)) {
				continue; } track.add(i); backtrack(nums, track); track.removeLast(); }}}Copy the code