# Java Solution, Backtracking

• Just try every possible number at each position...

``````public class Solution {
int count = 0;

public int countArrangement(int N) {
if (N == 0) return 0;
helper(N, 1, new int[N + 1]);
return count;
}

private void helper(int N, int pos, int[] used) {
if (pos > N) {
count++;
return;
}

for (int i = 1; i <= N; i++) {
if (used[i] == 0 && (i % pos == 0 || pos % i == 0)) {
used[i] = 1;
helper(N, pos + 1, used);
used[i] = 0;
}
}
}
}
``````

• This post is deleted!

• @shawngao
Hi ShawnGao,
This is a great solution. How do you think in terms of coding for a backtracking problem like this. I mean I could think of the solution for this problem in which either I had to make all the permutations and then count how many satisfy the condition for which I had to use some kind of recursion. But i was not able to get the code working i.e. I can code if it is a simple recursive problem like in a binary tree finding the maxDepth, etc but when it comes to this kind of problems I have been facing difficulty implementing it or thinking about the implementation hard. How do you approach these kinds of problems? Any suggestion on implementing these problems is helpful especially in a shorter duration such as interviews?
Thanks
Sumanth

• @mssumanth I would say `Practice Makes Perfect`.

A general recursive template for backtracking may look like this:

``````   helper (parameters of given data and current recursive level) {
// Handle base cases, i.e. the last level of recursive call
if (level == lastLevel) {
record result;
return sth;
}
// Otherwise permute every possible value for this level.
for (every possible value for this level) {
helper(parameters of given data and next recursive level);
}
return sth;
}
``````

• @shawngao Thanks a lot @shawngao :)

• can use bit manipulation to replace used boolean array

``````public class Solution {
public int countArrangement(int N) {
int[] cnt = new int[1];
int bit = 0;
dfs(N, cnt, bit, 1);
return cnt[0];
}

private void dfs(int N, int[] cnt, int bit, int step) {
if (step == N + 1) { cnt[0] ++; return; }
for (int i = 1; i<= N; i ++) {
if (((1 << i) & bit) > 0) continue;
if (step % i == 0 || i % step == 0)
dfs(N, cnt, (1 << i) | bit, step + 1);
}
}
}
``````

• Great solution!

Since `N <= 15`, initially I thought about simple brute force with `std::next_permutation` to go through every permutation of `{1, 2, ..., N}`, but it got TLE at input `N = 12` (because I didn't realize `15!` is actually in the magnitude of `10^12` :-) ).

Basically a rewritten version in C++:

``````    int count = 0, used = 0, pos = 1;

int countArrangement(int N) {
for (int i = 1; i <= N && pos <= N; i++)
if ((used & 1<<i) + (i%pos)*(pos%i) == 0)
used ^= 1<<i, ++pos, countArrangement(N), used ^= 1<<i, --pos;
return count += (pos > N);
}
``````

• @mssumanth

1. In Leetcode, there are many backTrack problems, some of which are good starting points.
Combination Sum, Factor Combinations, Permutations, Permutations II.
More advanced: Evaluate Division, Word Pattern II, Remove Invalid Parentheses, Basic Calculator
2. When solving a BT problem, pay attention to whether it's a Permutation problem, or a Combination.
The problem here is a permutation.

• @zzhai Thanks a lot @zzhai

• ``````used[i] = 1;
helper(N, pos + 1, used);
used[i] = 0;
``````

this is awesome!

thanks.

• @shawngao
in the helper function you don't have to iterate through 1 to N and use used[] array to tell a number is used or not. You can simply initialize the array to be nums[i] = i and in the helper function swap them so you just need iterate through pos to N. I think that's the standard back tracking

``````    private void helper(int[] nums, int start) {
if (start == nums.length) {
count++;
return;
}
for (int i = start; i < nums.length; i++) {
swap(nums, start, i);
if (nums[start] % start == 0 || start % nums[start] == 0) helper(nums, start+1);
swap(nums,i, start);
}
}
public int countArrangement(int N) {
if (N == 0) return 0;
int[] nums = new int[N+1];
for (int i = 0; i <= N; i++) nums[i] = i;
helper(nums, 1);
return count;
}
``````

• @shawngao
in the helper function you don't have to iterate through 1 to N and use used[] array to tell a number is used or not. You can simply initialize the array to be nums[i] = i and in the helper function swap them so you just need iterate through pos to N. I think that's the standard back tracking

Great point. I was also thinking that the values which have been used before should not be put in the loop again because we started with the original order `[1, 2, ..., N]` and we knew exactly what values have been tested.

Here is basically a rewritten version of your idea in C++. It speeds up from ~200ms to 60ms:

``````    int nums[16] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};

int countArrangement(int N, int s = 1) { // s: start index
for (int i = s; i <= N; i++)
if ((nums[i]%s)*(s%nums[i]) == 0)
swap(nums[i],nums[s]), countArrangement(N,s+1), swap(nums[i],nums[s]);
return nums[0] += (s>N);
}
``````

• @zzg_zzm
Actually start from the back is even faster. You can look at my 6ms version :)

• @shawngao Thanks a lot for sharing your code :)

• Clear java code

``````public class Solution {
public int countArrangement(int N) {
// arr[0] is reserved for sum
int[] array = new int[N + 1];
settle(N, array);
return array[0];
}

private void settle(int n, int[] array) {
if (n == 1) {
// 1 could be settled anywhere, sum++
array[0] ++;
return;
}
for (int i = 1; i < array.length; i ++) {
// check i is not occupied and fit n
if (array[i] == 0 && (n % i == 0 || i % n == 0)) {
// n is settled to i
array[i] = n;
// get n - 1 settled
settle(n - 1, array);
// backtrack
array[i] = 0;
}
}
}

}
``````

• @shawngao

``````public class Solution {
public int countArrangement(int n) {
boolean[] used = new boolean[n + 1];
return dfs(1, n, used);
}

private int dfs(int position, int n, boolean[] used) {
if (position == (n + 1)) {
return 1;
}

int count = 0;
for (int test = 1; test <= n; test ++) {
if (!used[test] && isBeautiful(position, test)) {
used[test] = true;
count += dfs(position + 1, n, used);
used[test] = false;
}
}

return count;
}

private boolean isBeautiful(int position, int value) {
return (position % value == 0) || (value % position == 0);
}
}
``````

• Another Java solution without global variable. Thanks for sharing!

``````    public int countArrangement(int N) {
return dfs(N, new boolean[N + 1], 1);
}

private int dfs(int n, boolean[] used, int k) {
if (k == n + 1) return 1;
int cnt = 0;
for (int i = 1; i <= n; i++) { // If not used and "beautiful", put number i in position k
if (used[i] || !(i % k == 0 || k % i == 0)) continue;
used[i] = true;
cnt += dfs(n, used, k + 1);
used[i] = false;
}
return cnt;
}
``````

• Is the time complexity O(n^n)?

• @ParinSanghavi

Backtracking is slow, but not as slow as O(n^n).

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.