Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 <= i <= N) in this array:
Now given N, how many beautiful arrangements can you construct?
Example 1:
Input: 2 Output: 2 Explanation: The first beautiful arrangement is [1, 2]: Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1). Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2). The second beautiful arrangement is [2, 1]: Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1). Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.
Note:
The description was taken from https://leetcode.com/problems/beautiful-arrangement/.
#O(K) Time, O(N) Spaceclass Solution: def countArrangement(self, N: int) -> int: count = 0 seen = set() def backtrack(start: int) -> None: nonlocal count if start > N: count += 1 return for i in range(1, N+1): if i not in seen and (i%start == 0 or start%i == 0): seen.add(i) backtrack(start+1) seen.remove(i) backtrack(1) return countIf a problem requires us to return all possible combinations of a given input, typically that is an indication that backtracking is a good approach.
Backtracking is a Depth-First Search algorithm where we remove a choice whenever the DFS path yoyo returns to the given function. This allows us to circulate elements into each valid position so that we can generate each valid combination.
A general template for backtracking is to set a base case that appends a valid combination for a given DFS path to the output, if not, check if a placement is valid then make the placement. Once that placement is made, we'd go down a new DFS path with that placement and if that path didn't lead to a solution or it didn't lead to every solution like in this problem, we'd backtrack on the choice to make that placement by removing it from the combination.
Let's start by initializing the count of beautiful arrangements that we will be returning, as well as the HashSet that keeps track of used values so that we don't reproduce duplicate permutations.
count = 0 seen = set()
Next, we will create our backtrack function.
The function will take a starting integer that will be the starting point for a function call's iteration to the input N value.
def backtrack(start: int) -> None:
The base case we will want to check at the beginning of each function call is if the starting integer has passed N.
If that happens then it means that we have produced a beautiful arrangement permutation that contains all of the integers from one to N, so we will increment our count and return from the current function.
Here we need to declare count as nonlocal so that Python knows the scope of the variable extends to the outer function. We could have declared it as a global variable or created a single index array to contain the value but this is a better practice.
nonlocal count if start > N: count += 1 return
We will now start creating the backtracking logic.
Let's create a loop that will iterate from one to N.
This is how we will split up the scope of each beautiful arrangement permutation through recursion.
for i in range(1, N+1):
According to our problem description, each number within the beautiful arrangement either needs to be divisible by the index, or the index needs to be divisible by the number.
If the starting number of the current function isn't in our set and either one of the previous statements is true, then we will add the current index to the set, recurse the function while incrementing the starting number, then backtrack by revering our change.
In this case, the change that we are backtracking is the addition of the index to the set.
if i not in seen and (i%start == 0 or start%i == 0): seen.add(i) backtrack(start+1) seen.remove(i)
We do this because we don't want to reconsider the same starting number position within the same Depth First Search path.
If the current index doesn't satisfy the two conditions of a beautiful arrangement, it will be skipped and the current function will iterate to the next index for consideration. This helps us prune the recursive tree.
Once we have our backtrack function built, all we need to do is make the initial call by passing one as the starting number.
Once all possible beautiful arrangements have been calculated, we will return the count.
backtrack(1) return count
The time complexity is set by the number of valid permutations we will have since our conditional statement will discard back DFS paths.
The space complexity is set by N since that is the highest call stack we will have and the greatest amount of numbers that would be in the seen set.