“This is the 21st day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

Topic describes

Given an array nums that does not contain duplicate digits, return all possible permutations. You can return the answers in any order.

Example 1:

Output: input: nums = [1, 2, 3], [[1, 2, 3], [31] 1,,1,3 [2], [2,3,1], [3,1,2], [3, 2, 1]]Copy the code

Example 2:

Input: nums = [0,1] output: [[0,1],[1,0]Copy the code

Example 3:

Input: nums = [1] Output: [[1]Copy the code

Tip:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • All integers in NUMs are different

[full array]

Thinking is introduced

We start with the outermost loop I =0 and then we add 1 to the path and then we go into the recursion, so we go into the middle loop I =0, no, because 1 is already in the path and I =1 in the middle loop, ok, we add 2 to the path, and then we go into the recursion, we go into the innermost loop I =0, no, I =1 in the innermost loop, no, Path.size ()==nums.length (); removeLast() =1; Path.removelast () : I =1; I =1; I =1; I =1; Add 2 to path, path is full again, save data again, jump. Remove layer I =1, leaving 1,3. Do the innermost layer I =2, no. And then I’m done running backtracking on the middle layer I =2, remove, I only have 1 in my path and then I’m done running backtracking on the outermost layer I =0, remove, I’m done running backtracking on the outermost layer I =1, The process is then repeated like this: nums.length, the number of times for

So path is null – > 1 – > 1, 2 – > 1, 2, 3 (result. Add) – > 1, 2 – > 1 – > 1, 3 – > 1 31 (result. Add) – > 1, 3 – > 1 – null – > 2 – > 2, 1-2,1,3 (result. Add) – >… – > 3, 2, 1 – >… Result.add (new LinkedList<>(path)) not result.add(path)

code

class Solution {
    LinkedList<Integer> path=new LinkedList<>();
    List<List<Integer>> result=new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        backtracking(nums);
        return result;
    }

    public void backtracking(int[] nums){
      
        if(path.size()==nums.length){
            result.add(new LinkedList<>(path));
            return;
        }
 
        for(int i=0;i<nums.length;i++){
           
            if(path.contains(nums[i])){
                continue;
            }
            path.add(nums[i]);
            backtracking(nums);
            path.removeLast();
                 
        }
    }
}

Copy the code

The results

Result: Yes

Execution time: 1 ms,

Memory consumption: 41.5MB