Backtracking - 46. Full arrangement

1 Title Description

Give an array without duplicate numbers nums , Back to its All possible permutations . You can In any order Return to the answer .

2 Title Example

Example 1：
Input ：nums = [1,2,3]
Output ：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2：
Input ：nums = [0,1]
Output ：[[0,1],[1,0]]

Example 3：
Input ：nums = [1]
Output ：[[1]]

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/permutations

3 Topic tips

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums All integers in Different from each other

backtracking :— An algorithm that finds all solutions by exploring all possible candidate solutions . If the candidate solution is confirmed to be not a solution ( Or at least not the last solution ), The backtracking algorithm will be carried out in the previous step — Some changes abandon the solution , Go back and try again .

4 Ideas

This problem can be regarded as a problem n A space arranged in a row , We need to fill in the given questions from left to right n Number , Each number can only be used once . So it's very direct to think — An exhaustive algorithm , That is, try to fill in a number from left to right , See if you can fill in this n A space , In the program, we can use 「 backtracking 」 To simulate this process .
We define recursive functions backtrack(first, output) It means to fill in from left to right first A place , Current arrangement is output. Then the whole recursive function is divided into two cases :

• If first = n, It means that we have completed n A place （ Pay attention to subscripts from О Start ), A feasible solution is found , We will output Put it in the answer array , Recursion ends .
• If first <n, We have to consider this second first Which number shall we fill in for each position . According to the requirements of the title, we certainly can't fill in the number that has been filled in , Therefore, it is easy to think of a processing method that we define a tag array vis To mark the number that has been filled in , Then fill in No first When the number is, we traverse the given n Number , If this number has not been marked , Let's try to fill in , And mark it , Continue trying to fill in the next position , Call the function backtrack( first＋ 1, output). When backtracking, the number and mark filled in this position should be cancelled , And continue to try other unmarked numbers .

It is a very intuitive idea to use tag array to deal with filled numbers , But can you remove this tag array ? After all, the tag array also increases the spatial complexity of our algorithm .
The answer is yes , We can give the subject n Array of Numbers nums Divided into left and right parts , The one on the left indicates the number that has been filled in , The right represents the number to be filled in , We only need to maintain this array dynamically during backtracking .
say concretely , Let's say we've filled in page first A place , that 、nums Array [0, first―1] Is a collection of filled numbers ,[first, n ―1] Is the set of numbers to be filled . We must be trying to use [first, n ―1] Fill in the number in first Number , Suppose the subscript of the number to be filled is i, Then when we're done, we'll go to the i Number and number first Number exchange , That is, it can make it possible to first＋1 When we count nums Array of [0, first] Part is the number filled in ,[first＋ 1,n―1] Is the number to be filled in , When you backtrack, you can complete the undo operation by switching back .
A simple example , Suppose we have [2,5,8,9,10] this 5 The number should be filled in , It has been filled in to 3 A place , It has been filled in [8,9] Two Numbers , So this array is now [8,9| 2,5,10] Such a state , The separator separates the left and right parts . Suppose we fill in this position 10 The number of , To maintain the array , We will 2 and 10 In exchange for , That is, the array can continue to keep the number to the left of the separator has been filled , The one on the right is to be filled in [8,9,10|2,5].
Of course, thoughtful readers must have found that the resulting full permutation is not stored in the answer array in dictionary order , If the title requires output in dictionary order , Then please use tag array or other methods .

5 My answer

class Solution {
    
    public List<List<Integer>> permute(int[] nums) {
    
        List<List<Integer>> res = new ArrayList<List<Integer>>();

        List<Integer> output = new ArrayList<Integer>();
        for (int num : nums) {
    
            output.add(num);
        }

        int n = nums.length;
        backtrack(n, output, res, 0);
        return res;
    }

    public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
    
        //  All the numbers have been filled in 
        if (first == n) {
    
            res.add(new ArrayList<Integer>(output));
        }
        for (int i = first; i < n; i++) {
    
            //  Dynamically maintain arrays 
            Collections.swap(output, first, i);
            //  Continue to recursively fill in the next number 
            backtrack(n, output, res, first + 1);
            //  Cancel the operation 
            Collections.swap(output, first, i);
        }
    }
}