46. Permutations

Permutations (Medium)
Given an array of distinct integers, we need to return every possible ordering of those numbers. The key idea in this solution is to build the permutation one position at a time by choosing one of the numbers that has not been used yet. That creates a decision tree where each path from top to bottom forms one complete permutation.

This solution uses backtracking, but it is still essentially brute force because it explores every possible arrangement. We build one working permutation, go deeper, and when we come back, we undo the last choice so we can try a different unused number in that position. When the current permutation reaches the same length as the input array, we copy it into the result.

Brute Force / Backtracking Solution:
Time Complexity: O(n · n!)
Space Complexity: O(n) extra space, not counting the output

There are n! total permutations because for the first position we have n choices, then n - 1 choices for the next position, then n - 2, and so on. For each finished permutation, we copy it into the result, and that copy takes O(n) time, which gives the full time complexity of O(n · n!). The recursion stack only goes as deep as the length of the array, and the used list is also size n, so the extra working space is O(n).

A very important detail is res.append(curr[:]). We do that because curr is the same list being reused throughout the recursion. We keep modifying it with append() and pop(), so we must save a copy of its current state when a permutation is complete. Also, pop() and used[i] = False are what make backtracking work: they undo the last choice so we can reuse the same list and bookkeeping array and explore the next branch cleanly. Another important detail is that the recursion happens inside the for loop. That is okay because each recursive call explores all possibilities under one choice, then returns control back to the loop so the next unused number can be tried.

Видео 46. Permutations канала JunCodes