C# - recursive DFS with backtracking


  • 0

    it is stated that N is no larger than 15 so we know we can use brute force to figure this out.

        public int CountArrangement(int N) {
            return Count (N, 1, new bool[N + 1]);
        }
        
        public int Count(int n, int pos, bool[] used)
        {
            if (pos > n) return 1;
            
            int cnt = 0;
            for (int u = 1; u <= n; u++)
            {
                if (!used[u] && (u % pos == 0 || pos % u == 0))
                {
                    used[u] = true;
                    cnt += Count(n, pos + 1, used);
                    used[u] = false;
                }
            }
            return cnt;
        }
    

Log in to reply
 

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