# A brief analysis of backtracking algorithm

2022-01-27 03:35:48

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){

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
visited[i] = 1;
backtrack(result, tmp, nums, visited);
tmp.remove(tmp.size()-1);
visited[i] = 0;
}
}
``````
``````      if(tmp.size() == nums.length){
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
visited[i] = 1;
backtrack(result, tmp, nums, visited);
tmp.remove(tmp.size()-1);
visited[i] = 0;
}
``````