Lintcode15 Permutations solution problem solution

[topic description]

Given a list of numbers, return all possible permutations.

Notice:You can assume that there is no duplicate numbers in the list.

Given a list of numbers, returns all its possible permutations.

Note: you can assume that there are no repeated numbers.

[topic link]

Http://www.lintcode.com/en/problem/permutations/

[topic Analysis]

When we encounter this kind of problem, obviously, the first idea is that we first go back to DFS and recursively solve it. For each element in the array, we find the Permutations headed by him, which requires that in recursion, we have to start traversing from the first element of the array. In this way, another problem is introduced. We will visit the same element many times, which is not the answer we want. So we introduced an array of type bool to record which element was traversed (find the corresponding by subscript). In solving each Permutation, if we visit this element, we set it to true in the bool array of the following table. After the visit, we set it to false.

Time complexity analysis: this problem is the same as Combination, so for the solution to this problem, the time complexity is also the same

O (n!)

[answer link]

Https://www.jiuzhang.com/solutions/permutations/