This is the 14th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Recommended reading

  • CSDN home page
  • GitHub open source address
  • Unity3D plugin sharing
  • Jane’s address book
  • My personal blog
  • QQ group: 1040082875

Hello, everyone, I am a little Magic dragon, Unity3D software engineer, VR, AR, virtual simulation direction, update software development skills from time to time, life perception, remember to use one button three links.

A, the title

1. Algorithm topic

“Given an array without duplicate digits, return all possible permutations.”

Title link:

Source: LeetCode

Link: 46. Full Permutation – LeetCode (leetcode-cn.com)

2

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

Example 1: input: nums = [1, 2, 3] output: [[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

Second, the problem solving

1. Analysis of ideas

When you see the words return all results, you need to think about whether you can use backtracking.

Backtracking: An algorithm that finds all possible solutions by exploring all possible candidates. If the candidate is determined not to be a solution, or at least not the last solution, the backtracking algorithm will discard the solution by making some changes in the previous step, i.e. backtracking and trying again.

In this problem, you can arrange each of these combinations, and it’s pretty straightforward to think of an exhaustive algorithm, where you take everything from left to right and combine it.

2. Code implementation

Code reference:

public class Solution {
    IList<IList<int>> list = new List<IList<int> > ();public IList<IList<int>> Permute(int[] nums) {
        IList<int> l = new List<int> (); Test(l, nums);return list;
    }

    void Test(IList<int> l, int[] nums)
    {
        if (nums.Length == l.Count)
        {
            // l.toarray () implements deep copy to prevent RemoveAt from pointing to the original object
            list.Add(l.ToArray());
            return;
        }

        for (int i = 0; i < nums.Length; i++)
        {
          if (l.Contains(nums[i]))
              continue;
            l.Add(nums[i]);
            Test(l, nums);
            l.RemoveAt(l.Count - 1); }}}Copy the code

3. Time complexity

Time complexity: O(n x n!

Where n is the length of the sequence.

Space complexity: O(n)

Where n is the length of the sequence.

Third, summary

This kind of problem is the same type, using backtracking algorithm!

In fact, the key to backtracking is: if it’s not appropriate, go back one step

Then, the time complexity is reduced by constraints.