C++ iterative backtracking solution using dynamic array and stack


  • 0
    M
    bool Divisible(int i, int j){
        if(i <= 0 || j <= 0) return false;
        return i % j == 0 || j % i == 0;
    }
    
    bool IsVisited(int* visited, int val, int pos){
        bool res = false;
        for(int i = 0; i < pos; ++i){
            if(visited[i] == val){
                res = true;
                break;
            }
        }
        return res;
    }
    
    int countArrangement(int N) {
        int cnt = 0;
        for(int i = 1; i <= N; ++i){
            int* visited = new int[N]{0};
            stack<pair<int, int>> st;
            int pos = 1;
            st.push(pair<int, int>(pos, i));
            while(!st.empty()){
                pair<int, int> pr = st.top();
                st.pop();
                visited[pr.first - 1] = pr.second;
                pos = pr.first + 1;
                
                if(pr.first == N){
                    cnt++;
                    continue;
                }
                
                for(int j = 1; j <= N; ++j){
                    if(!IsVisited(visited, j, pos- 1) && Divisible(j, pos)){
                        st.push(pair<int, int>(pos, j));
                    }
                }
            }
            delete [] visited;
        }
        return cnt;   
    }
    

Log in to reply
 

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