Classic recursive backtracking problem and solution
Another one from LeetCode: https://leetcode.com/problems/beautiful-arrangement/?tab=Description, or with the description here:
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:
- The number at the ith position is divisible by i.
- i is divisible by the number at the ith position.
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:
- N is a positive integer and will not exceed 15.
Given the small N (15), it is relatively straightforward to come up with a recursive backtracking solution for this. To remind the fundamentals:
- Recursive backtracking is expensive since it will generate all the solutions
- Usually such problems (especially the ones asking for the number of solutions only) can be further optimized into non-recursive dynamic programming (DP). The challenge is to derive the proper DP function based on solutions to subsets of the problem
- The recursive backtracking goes as follows:
- Have a base case where you increment the solution at that point
- Keep track of solutions already used (Hash table is your friend here)
- The induction calls recursively whenever you're able to fit a partial solution candidate for the current position
Here is the code, cheers, Marcelo.
public class Solution
{
public int CountArrangement(int N)
{
int retVal = 0;
CountArrangementInternal(1, N, new Hashtable(), ref retVal);
return retVal;
}
private void CountArrangementInternal(int currentPosition,
int maxValue,
Hashtable numbersAlreadyUsed,
ref int solutions)
{
if (currentPosition > maxValue)
{
solutions++;
return;
}
//Find all the posible unused numbers that fit current position
for (int i = 1; i <= maxValue; i++)
{
if (!numbersAlreadyUsed.ContainsKey(i) &&
(i % currentPosition == 0 || currentPosition % i == 0))
{
numbersAlreadyUsed.Add(i, true);
CountArrangementInternal(currentPosition + 1,
maxValue,
numbersAlreadyUsed,
ref solutions);
numbersAlreadyUsed.Remove(i);
}
}
}
}
Nice solution, Marcelo! You could have also used a boolean array to track used numbers instead of hashtable to speed things up, but otherwise it's totally legit :) Since I also wanted to see arrangements I used a vector for an arrangement representation and it's still very performant (beats more than 60% of other c++ submissions):
ReplyDeleteclass Solution {
private:
int countArrangement(vector& arrangement, int idx) {
if (arrangement.size() == idx) return 1;
int count = 0;
for (int i = idx; i < arrangement.size(); ++i) {
if (arrangement[i] % idx && idx % arrangement[i]) continue;
swap(arrangement[idx], arrangement[i]);
count += countArrangement(arrangement, idx+1);
swap(arrangement[idx], arrangement[i]);
}
return count;
}
public:
int countArrangement(int N) {
vector arrangement(N+1);
iota(arrangement.begin(), arrangement.end(), 0);
return countArrangement(arrangement, 1);
}
};