This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.
Another day another banger in the leetcode game. Backtracking was never my thing, or maybe my brain is just fed up with my bullshit. DFS is it's close sibling and luckily I know DFS pretty dang well and after reading this webpage, it became much clearer. This video also help in making it less complicated than I thought. Maybe the problem is just my imagining the code be more complicated than it needs to be.
According to these resources, the way you approach backtracking questions like a newbie is as follows:
1.) create a brute-force solution:
var countArrangement = function(n) {
const attempts = [];
function recurr(position, array) {
if(position > n) {
attempts.push(array);
return;
}
for (let index=1; index<=n; index++) {
const newArray = array.slice()
newArray.push(index);
recurr(position+1, newArray)
}
}
recurr(1,[]);
return attempts.filter(function(numPermutation){
return [...new Set(numPermutation)].length === n &&
numPermutation.every(isBeautiful)
}).length;
};
function isBeautiful (permI, index) {
return (index+1) % permI === 0 || permI % (index+1) === 0;
}
the following array for n = 3 would be created in order:
111
112
113
121 ...
if you can understand why it proceeds like this and in this exact order then congratulation, you understood the brute force solution, and we can move on! You can see the full array by console.log(attempts) right before the return.
2.) identify the source of unnecessary calculation:
for this problem it is rather obvious once you have the brute force solution. The repeated conditions are explicit in the filter function at the return: unique numbers in array and whether every element number is beautiful in array.
3.) It is easier to see the code for checking whether a number is beautiful: you just check whether the number is beautiful right before you push it:
function recurr(position, array) {
...
for (let index=1; index<=n; index++) {
if (!isBeautiful(index, position)) {
continue;
}
const newArray = array.slice();
newArray.push(index);
recurr(position+1, newArray)
...
At this point we have pretty big improvement since we are at least not literally doing every single possible permutation, which is O(N^N). However, we are still lacking since there are still a lot of invalid permutations, such as all 1s.
4.) remove all arrays with repeated number in said array. This part is much harder for me, luckily from my previous failures I had a hint for how to get it correctly.
Before getting into it, let's quickly change a few things since we are filtering out non-unique number arrays, we don't need to remember all the arrays anymore that's a nightmare for space complexity. To achieve this, we first remove attemps[] and add in "let numBeautiful = 0;". In the recursion, we are no longer ending the recursion by pushing to array, we are simply numBeautiful++ and we return numBeautiful as final result.
Then onto the remove non-unique part. To understand, we have to go back to the first brute force code and observe how the code is proceeding:
111
112
113
121 ...
specifically at 113 to 121, it proceeds more like this
113 -> 11 -> 1 -> 12 -> 121
this is where having a visualization like a tree helps:
Each node is an iteration of the recursion, specifically inside the for loop. Therefore we see an opportunity where we can add and remove used numbers sequentially without possible conflict.
let's say for n = 6:
we proceed like this (without checking isbeautiful for simplicity sake):
12345
123451 -> 123452 -> 123453 -> 123454 -> 123455
123456
12346 -> ...
123465 ...
1235 -> 12351 ...
... 123564
each line represents a successful proceeding to the next recursion, aka passing uniqueness test. -> means not passing therefore inside for loop.
So the idea is that we can add a memoization on whether a number has been used yet at each step. Crazy wording alert below:
At the first step listed, 12345, all 5 of these numbers are inside the memoization. Then at 123451 step, we are checking against the memoization, it failed that's why it -> to the next number until 123456 to the next line.
Between 123456 and 12346, what we are actually doing:
remove 5 from memo, go to the 6 aka number in the for loop, memoize 6, proceed via 12346 until we find 123465.
After 123465 we are removing first 5 from memoization, then proceed up the tree to the iteration with 6 to remove 6 from memoization to the iteration with 4. We then remove 4 from memoization and proceed with 5, which we add to memorization.
This exactly mess above is hard to follow for sure, but be more patient with it so that it burns into your mind and you'll never have problem with backtracking again.
Below is the full code:
var countArrangement = function(n) {
const oneToN = [0];
for (let i=1; i<=n; i++) {
oneToN.push(i);
};
let numBeautiful = 0;
const numbersUsed = new Array(n);
function recurr(position, array) {
if(position > n) {
numBeautiful++;
return;
}
for (let index=1; index<=n; index++) {
if (!isBeautiful(index, position) || numbersUsed[index]) {
continue;
}
const newArray = array.slice()
newArray.push(index);
numbersUsed[index] = true;
recurr(position+1, newArray)
numbersUsed[index] = false;
}
}
recurr(1,[]);
return numBeautiful;
};
function isBeautiful (permI, index) {
return (index) % permI === 0 || permI % (index) === 0;
}
Note that the beauty in this is that we have 1 single constant array that checks whether a number is used or not. So we are avoid like a billion bits vs the first code that stores all the possible arrays.
numbersUsed[index] = true;
recurr(position+1, newArray)
numbersUsed[index] = false;
These three lines is where my mess of paragraph describing what it does, shocking how little code it translates to right?
At least I made some progress today, hopefully this helps you a bit. I'll probably come back to edit this so it reads better later in the day.
Let me know anything on your mind after reading through this, THANKS!
Top comments (0)