C++ solution with back-tracking and hash set


  • 0
    P
    private:
        unordered_set<int> hset;
    public:
        // back tracking
        // 枚举所有可能的情况
        // tc: o(n!)
        int countArrangement(int N) {
            if (hset.size() == N) { // 哈希表里面元素的个数表示装了多少个,如果装满则返回1
                return 1;
            }
            int cnt = 0;
            int sz = hset.size() + 1; // 下标需要加1
            for (int i = 1; i <= N; i++) {
                if (hset.count(i)) {
                    continue;
                }
                if (i % sz == 0 || sz % i == 0) {
                    hset.insert(i);
                    cnt += countArrangement(N);
                    hset.erase(i);
                }
            }
            return cnt;
        }
        
    };```

Log in to reply
 

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