A brief analysis of backtracking algorithm

Backtracking algorithm

A very easy algorithm . Generally speaking, it is to convert all data into a tree structure , Go down one by one , An algorithm that can't go down and can go back .

Example 1 Arrays return values in different permutations

Given a repeatable array , Combine into different sets in different order , How many kinds? . What are the differences ？

int scores2[] = new int[]{
    1,2,3};

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

int scores2[] = new int[]{
    1,3,3};

[1, 3, 3]
[3, 1, 3]
[3, 3, 1]

The backtracking method is used here , Return to one list Of list aggregate , The argument is an array .
Define the first variable visited It is used to save whether all possible steps have been completed or whether the current steps have been done , The same as the length of the array in the parameter , Used to record those steps , Those didn't go .
result Result set
tmp The value that satisfies the condition
First, sort the array

 public static List<List<Integer>> getCombination(int[] nums) {
    
	        int[] visited = new int[nums.length];
	        ArrayList<List<Integer>> result = new ArrayList<>();
	        ArrayList<Integer> tmp = new ArrayList<>();
	        Arrays.sort(nums);// Sort 
	        backtrack(result, tmp, nums, visited);
	        return result;
	    }

backtrack It means backtracking , Incoming result set , The value that satisfies the condition , Array , And step records

public void backtrack(ArrayList<List<Integer>> result, ArrayList<Integer> tmp, int[] nums, int[] visited) {
    
	        if(tmp.size() == nums.length){
    
	            result.add(new ArrayList<>(tmp));
	            return;
	        } 
	        for(int i = 0; i < nums.length; i++){
    
	            if (visited[i] == 1) continue;           
	            if(i > 0 && nums[i-1] == nums[i] && visited[i-1] != 0) continue;// prune 
	            tmp.add(nums[i]);
	            visited[i] = 1;
	            backtrack(result, tmp, nums, visited);
	            tmp.remove(tmp.size()-1);
	            visited[i] = 0;
	        }
	    }

      if(tmp.size() == nums.length){
          result.add(new ArrayList<>(tmp));
          return;
      }

If the value satisfies the condition, it will be added to the result , Jump straight out of the loop .

Traversal condition array , If the current step goes , Then jump out of the current .
If the current value is equal to the previous value , And the last value has gone , Then jump out of the current .
Add to the array , The current step record has gone , Current number of iterations .
Subtract the added thought , Change the current step to not go .

  for(int i = 0; i < nums.length; i++){
    
	            if (visited[i] == 1) continue;           
	            if(i > 0 && nums[i-1] == nums[i] && visited[i-1] != 0) continue;// prune 
	            tmp.add(nums[i]);
	            visited[i] = 1;
	            backtrack(result, tmp, nums, visited);
	            tmp.remove(tmp.size()-1);
	            visited[i] = 0;
	        }