Share my C++ solution. Use recursion for generating possibilities combination


  • 0
    S
    class BeautifulArrangementSolution {
    public:
        int countArrangement(int N) {
            std::vector<std::set<int>> possibleValues;
            generatePossibilities(N, possibleValues);
            
            int level = 0;
            int count = 0;
            std::vector<int> selectedStack;
            countCombinations(possibleValues, selectedStack, level, count);
            
            return count;
        }
    private:
        void generatePossibilities(int N, std::vector<std::set<int>> &possibleValues)
        {
            possibleValues.reserve(N+1);
            possibleValues.push_back(std::set<int>());
            
            for (int i = 1; i <= N; ++i) {
                std::set<int> values;
                for (int j = 1; j <= N; ++j) {
                    if (j%i == 0 || i%j == 0) {
                        values.insert(j);
                    }
                }
                possibleValues.push_back(values);
            }
        }
        
        void countCombinations(const std::vector<std::set<int>> &possibleValues, std::vector<int> &selectedStack, int level, int &count)
        {
            if (level >= possibleValues.size()-1) {
                ++count;
                return;
            }
            ++level;
    
            const std::set<int> &values = possibleValues[level];
            for (std::set<int>::iterator it = values.begin(); it != values.end(); ++it) {
                int value = *it;
                if (std::find(selectedStack.begin(), selectedStack.end(), value) != selectedStack.end()) {
                    continue;
                }
                selectedStack.push_back(value);
                countCombinations(possibleValues, selectedStack, level, count);
                selectedStack.pop_back();
            }
            --level;
        }
    };
    

Log in to reply
 

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